# formula for sequences satisfying second order recurrence relations

###### 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}$:

 $\displaystyle s_{n+1}$ $\displaystyle=As_{0}\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}B^{k}A% ^{n-2k}+Bs_{0}\sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}B^{k}A^{% n-1-2k}$ $\displaystyle=s_{0}\left(\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}B% ^{k}A^{n+1-2k}+\sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}B^{k+1}% A^{n-1-2k}\right)$ $\displaystyle=s_{0}\left(A^{n+1}+\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}\binom{% n-k}{k}B^{k}A^{n+1-2k}+\sum_{k=1}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n-k}{k-1% }B^{k}A^{n+1-2k}\right)$

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:

 $\displaystyle s_{n+1}$ $\displaystyle=s_{0}\left(A^{n+1}+\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}\binom{% n-k}{k}B^{k}A^{n+1-2k}+\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k-1}B% ^{k}A^{n+1-2k}+B^{\frac{n+1}{2}}\right)$ $\displaystyle=s_{0}\left(A^{n+1}+\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}\left[% \binom{n-k}{k}+\binom{n-k}{k-1}\right]B^{k}A^{n+1-2k}+B^{\frac{n+1}{2}}\right)$ $\displaystyle=s_{0}\left(A^{n+1}+\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor}\binom{% n+1-k}{k}B^{k}A^{n+1-2k}+B^{\frac{n+1}{2}}\right)$ $\displaystyle=s_{0}\sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n+1-k}{k}B^{% k}A^{n+1-2k}$

Now assume that $n$ is even. Then the two summations have the same number of terms and can be combined as is:

 $\displaystyle s_{n+1}$ $\displaystyle=s_{0}\left(A^{n+1}+\sum_{k=1}^{\lfloor\frac{n+1}{2}\rfloor}\left% [\binom{n-k}{k}+\binom{n-k}{k-1}\right]B^{k}A^{n+1-2k}\right)$ $\displaystyle=s_{0}\sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n+1-k}{k}B^{% k}A^{n+1-2k}$

Hence, the theorem holds for all nonnegative integers $n$. ∎

Title formula for sequences satisfying second order recurrence relations FormulaForSequencesSatisfyingSecondOrderRecurrenceRelations 2013-03-22 17:51:43 2013-03-22 17:51:43 Wkbj79 (1863) Wkbj79 (1863) 7 Wkbj79 (1863) Theorem msc 11B37 msc 03D20