Recurrence relations

Special Example:
Find a closed-form formula for the Fibonacci sequence defined by $F_{n+1}=F_{n}+F_{n-1}, n>0, F_0=0, F_1=1$.

Characteristic equation:
$x^2-x-1=0$
$\large x_1=\phi=\frac{1+\sqrt{5}}{2}, x_2=-\phi^{-1}=\frac{1-\sqrt{5}}{2}$

General solution for the recurrence:
$\large F_n=c_1\frac{1+\sqrt{5}}{2}+c_2\frac{1-\sqrt{5}}{2}$

Using the initial conditions,
$\large{ c_1+c_2=0, c_1\phi-c_2\phi^{-1}=1 \Rightarrow c_1=\frac{1}{\sqrt{5}}, c_2=-\frac{1}{\sqrt{5}}\\
F_n=\frac{1}{\sqrt{5}}[\phi^n-(-\phi^{-1})^n]}$

Arithmetic Sequence
$a_n=a_{n-1}+d=a_0+dn$

Example:
$1, 4, 7, 10, 13, ...\\
a_0=1\\
a_n=a_{n-1}+3=a_0+3n=1+3n$

Geometric Sequence
$a_n=r\cdot a_{n-1}=r^n\cdot a_0$

Example:
$1, 4, 16, 64, 256, ...\\
a_0=1\\
a_n=4a_{n-1}=4^n \cdot a_0=4^n$

Polynomial
$a_n=a_{n-1}+p(n)$

Example:
$5, 0, -8, -17, -25, -30, ...\\
a_0=5\\
a_n=a_{n-1}+p(n)\\
a_1=a_0+p(1) \Rightarrow p(1)=-5\\
p(2)=-8, p(3)=-9, p(4)=-8, p(5)=-5\\
p(n)=n^2-6n$

Any recursion will have a polynomial closed form formula of degree one higher than the degree of p. [?]

Thus, $a_n=c_3n^3+c_2n^2+c_1n+c_0$.
It remains to solve the linear system:
$c_0=5\\
c_3+c_2+c_1+c_0=0\\
8c_3+4c_2+2c_1+c_0=-8\\
27c_3+9c_2+3c_1+c_0=-17\\
\large{c_3=\frac{1}{3},c_2=-\frac{5}{2},c_1=-\frac{17}{6},c_0=5\\
a_n=\frac{1}{3}n^3-\frac{5}{2}n^2-\frac{17}{6}n+5}$

Linear Combination

Example:
$1, 4, 13, 46, 157, ...\\
a_0=1, a_1=4\\
a_n=2a_{n-1}+5a_{n-2}$

Characteristic equation:
$x^2=2x+5\\
x^2-2x-5=0\\
x=1\pm \sqrt{6}$

General solution for the recurrence:
$a_n=c_1(1+\sqrt{6})^n+c_2(1-\sqrt{6})^n$

Using the initial conditions,
$c_1+c_2=1, c_1(1+\sqrt{6})+c_2(1-\sqrt{6})=4\\
\large{ c_1=\frac{2+\sqrt{6}}{4}, c_2=\frac{2-\sqrt{6}}{4}\\
a_n=\frac{2+\sqrt{6}}{4}(1+\sqrt{6})^n+\frac{2-\sqrt{6}}{4}(1-\sqrt{6})^n}$

Generating Functions
$A(x)=\sum_{k=0}^\infty a_k x^k$

A generating function is a formal power series where the coefficient of $x^n$ is the nth term of the sequence.

Example:
$2, 5, 14, 41, 122, ...\\
a_0=2, a_n=3a_{n-1}-1$

$\large{A(x)\\
=\sum_{k=0}^\infty a_k x^k\\
=2+\sum_{k=1}^\infty a_k x^k\\
=2+\sum_{k=1}^\infty(3a_{k-1}-1)x^k\\
=2+\sum_{k=1}^\infty3a_{k-1}x^k-\sum_{k=1}^\infty x^k\\
=2+\sum_{k=1}^\infty3xa_{k-1}x^{k-1}-\sum_{k=1}^\infty x^k\\
=2+3xA(x)-\frac{x}{1-x}\\
(3x-1)A(x)=\frac{x}{1-x}-2}$

$\large{\begin{align}A(x) &= \frac{\frac{x}{1-x}-2}{3x-1}\\
&=\frac{3x-2}{(3x-1)(1-x)}\\
&=\frac{3}{2}\frac{1}{1-3x}+\frac{1}{2}\frac{1}{1-x}\\
&=\frac{3}{2}(1+3x+9x^2+...+3^kx^k+...)+\frac{1}{2}(1+x+x^2+...+x^k+...)\\
&=\sum_{k=0}^\infty \frac{3^{k+1}+1}{2} x^k\\
\end{align}}$

$\large a_n=\frac{3^{n+1}+1}{2}$

[Click here for a review on methods of partial fractions.]

Explanations:
[later]

Applications
Matrix
[later]

Probability
[later]

More to explore:
difference equations
dynamical systems
Mandelbrot and Julia set
logistic equation

Question:
Can we always find the nth term of a sequence?