formula for sequences satisfying second order recurrence relations

Theorem.

Let $\mathrm{\{}{s}_n\mathrm{\}}$ be a sequence such that there exist constants $A\mathrm{,}B\mathrm{\in }\mathrm{C}$ with $s_{\mathrm{1}}\mathrm{=}A\mathit{}{s}_{\mathrm{0}}$ and, for all positive integers $n$,

$$s_{n+1}=A{s}_n+B{s}_{n-1}.$$

Then for all nonnegative integers $n$, we have

$$s_n=s_0\sum _{k=0}^{\lfloor \frac{n}{2}\rfloor }\left(\genfrac{}{}{0pt}{}{n-k}{k}\right)B^k{A}^{n-2k},$$

where $\mathrm{\lfloor }\mathrm{\cdot }\mathrm{\rfloor }$ denotes the floor function and $\mathrm{\left(}\genfrac{}{}{0pt}{}{a}{r}\mathrm{\right)}$ 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\left(\genfrac{}{}{0pt}{}{0-k}{k}\right)B^k{A}^{0-2k}.$$

• If $n=1$, then

  $$s_1=A{s}_0=s_0\sum _{k=0}^0\left(\genfrac{}{}{0pt}{}{1-k}{k}\right)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}=A{s}_n+B{s}_{n-1}.$$

We can use the induction hypothesis on $s_n$ and $s_{n-1}$:

$s_{n+1}$ $=A{s}_0{\displaystyle \sum _{k=0}^{\lfloor \frac{n}{2}\rfloor }}\left({\displaystyle \genfrac{}{}{0pt}{}{n-k}{k}}\right)B^k{A}^{n-2k}+B{s}_0{\displaystyle \sum _{k=0}^{\lfloor \frac{n-1}{2}\rfloor }}\left({\displaystyle \genfrac{}{}{0pt}{}{n-1-k}{k}}\right)B^k{A}^{n-1-2k}$

$=s_0\left({\displaystyle \sum _{k=0}^{\lfloor \frac{n}{2}\rfloor }}\left({\displaystyle \genfrac{}{}{0pt}{}{n-k}{k}}\right)B^k{A}^{n+1-2k}+{\displaystyle \sum _{k=0}^{\lfloor \frac{n-1}{2}\rfloor }}\left({\displaystyle \genfrac{}{}{0pt}{}{n-1-k}{k}}\right)B^{k+1}{A}^{n-1-2k}\right)$

$=s_0\left(A^{n+1}+{\displaystyle \sum _{k=1}^{\lfloor \frac{n}{2}\rfloor }}\left({\displaystyle \genfrac{}{}{0pt}{}{n-k}{k}}\right)B^k{A}^{n+1-2k}+{\displaystyle \sum _{k=1}^{\lfloor \frac{n+1}{2}\rfloor }}\left({\displaystyle \genfrac{}{}{0pt}{}{n-k}{k-1}}\right)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:

$s_{n+1}$ $=s_0\left(A^{n+1}+{\displaystyle \sum _{k=1}^{\lfloor \frac{n}{2}\rfloor }}\left({\displaystyle \genfrac{}{}{0pt}{}{n-k}{k}}\right)B^k{A}^{n+1-2k}+{\displaystyle \sum _{k=1}^{\lfloor \frac{n}{2}\rfloor }}\left({\displaystyle \genfrac{}{}{0pt}{}{n-k}{k-1}}\right)B^k{A}^{n+1-2k}+B^{\frac{n+1}{2}}\right)$

$=s_0\left(A^{n+1}+{\displaystyle \sum _{k=1}^{\lfloor \frac{n}{2}\rfloor }}\left[\left({\displaystyle \genfrac{}{}{0pt}{}{n-k}{k}}\right)+\left({\displaystyle \genfrac{}{}{0pt}{}{n-k}{k-1}}\right)\right]B^k{A}^{n+1-2k}+B^{\frac{n+1}{2}}\right)$

$=s_0\left(A^{n+1}+{\displaystyle \sum _{k=1}^{\lfloor \frac{n}{2}\rfloor }}\left({\displaystyle \genfrac{}{}{0pt}{}{n+1-k}{k}}\right)B^k{A}^{n+1-2k}+B^{\frac{n+1}{2}}\right)$

$=s_0{\displaystyle \sum _{k=0}^{\lfloor \frac{n+1}{2}\rfloor }}\left({\displaystyle \genfrac{}{}{0pt}{}{n+1-k}{k}}\right)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:

$s_{n+1}$ $=s_0\left(A^{n+1}+{\displaystyle \sum _{k=1}^{\lfloor \frac{n+1}{2}\rfloor }}\left[\left({\displaystyle \genfrac{}{}{0pt}{}{n-k}{k}}\right)+\left({\displaystyle \genfrac{}{}{0pt}{}{n-k}{k-1}}\right)\right]B^k{A}^{n+1-2k}\right)$

$=s_0{\displaystyle \sum _{k=0}^{\lfloor \frac{n+1}{2}\rfloor }}\left({\displaystyle \genfrac{}{}{0pt}{}{n+1-k}{k}}\right)B^k{A}^{n+1-2k}$

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

Title	formula for sequences satisfying second order recurrence relations
Canonical name	FormulaForSequencesSatisfyingSecondOrderRecurrenceRelations
Date of creation	2013-03-22 17:51:43
Last modified on	2013-03-22 17:51:43
Owner	Wkbj79 (1863)
Last modified by	Wkbj79 (1863)
Numerical id	7
Author	Wkbj79 (1863)
Entry type	Theorem
Classification	msc 11B37
Classification	msc 03D20