Theorem   Let $\{s_n\}$ be a sequence such that there exist constants $A,B\in\mathbb{C}$ with $s_1=As_0$ and, for all positive integers $n$ , $$ s_{n+1}=As_n+Bs_{n-1}. $$ Then for all nonnegative integers $n$ , we have $$ s_n=s_0\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n-k}{k} B^k A^{n-2k}, $$ where $\lfloor\cdot\rfloor$ denotes the floor function and $\binom{a}{r}$ denotes the binomial coefficient.

Proof. This will be proven by induction. Due to the presence of $\lfloor\frac{n}{2}\rfloor$ , odd $n$ and even $n$ should be considered separately. Thus, there are two base steps:

• If $n=0$ , then $$ s_0=s_0\sum_{k=0}^0 \binom{0-k}{k} B^k A^{0-2k}. $$
• If $n=1$ , then $$ s_1=As_0=s_0\sum_{k=0}^0 \binom{1-k}{k} B^k A^{1-2k}. $$

Now assume that the theorem holds for all nonnegative integers less than or equal to some positive integer $n$ . We must show that the theorem holds for $n+1$ .

Recall that $$ s_{n+1}=As_n+Bs_{n-1}. $$ We can use the induction hypothesis on $s_n$ and $s_{n-1}$ :

First assume that $n$ is odd. Then the first of the two summations has $\lfloor\frac{n}{2}\rfloor=\frac{n-1}{2}$ terms and the second summation has $\lfloor\frac{n+1}{2}\rfloor=\frac{n+1}{2}$ terms. Therefore, we must split off the $k=\frac{n+1}{2}$ term from the second summation before combining the two summations:
Now assume that $n$ is even. Then the two summations have the same number of terms and can be combined as is:
Hence, the theorem holds for all nonnegative integers $n$ .