**Summary: This blog talks about solving two kinds of simple recursions: $F(n+1)=aF(n)+b$ and $F(n+1)=aF(n)+bF(n-1)$**↵
↵
###### 1. Preliminary Knowledge↵
(1) The solution of recursion $F(n+1)=aF(n)$ is $F(n)=a^{n-1}F(1)$.↵
↵
(2) The solution of recursion $F(n+1)=F(n)+a$ is $F(n)=(n-1)a+F(1)$.↵
↵
(3) The recursion $F(n+1)=kF(n)$ is the same as $F(n)=kF(n-1)$, also $F(n+1)=aF(n)+bF(n-1)$ is the same as $F(n)=aF(n-1)+bF(n-2)$ in this blog.↵
↵
###### 2. Solving $F(n+1)=aF(n)+b$, $a, b$ are constants, $a>1$↵
**The main idea is to create another function G(n) that satisfy $G(n)=kG(n-1)$ with constant k, solve G(n), and then solve F(n).**↵
↵
$F(n+1)=aF(n)+b$↵
↵
$F(n+1)=aF(n)+\frac{ab-b}{a-1}$↵
↵
$F(n+1)=a(F(n)+\frac{b}{a-1})-\frac{b}{a-1}$↵
↵
$F(n+1)+\frac{b}{a-1}=a(F(n)+\frac{b}{a-1})$↵
↵
Let $G(n)=F(n)+\frac{b}{a-1}$ we have↵
↵
$G(n)=aG(n-1)$↵
↵
$G(n)=a^{n-1}G(1)$↵
↵
$F(n)+\frac{b}{a-1}=a^{n-1}(F(1)+\frac{b}{a-1})$↵
↵
$F(n)=a^{n-1}(F(1)+\frac{b}{a-1})-\frac{b}{a-1}$↵
↵
###### 3. Solving $F(n+1)=aF(n)+bF(n-1)$, $a, b$ are constants↵
**The main idea is also to create $G(n)$, but the method is different, and the function $G(n)$ is more complicated.**↵
↵
$F(n+1)=aF(n)+bF(n-1)$↵
↵
Let $\alpha, \beta$ be two real numbers that satisfy $\alpha+\beta=a, \alpha\beta=-b, \alpha\le\beta$ we have↵
↵
$F(n+1)=(\alpha+\beta)F(n)-\alpha\betaF(n-1)$↵
↵
$F(n+1)-\alphaF(n)=\betaF(n)-\alpha\betaF(n-1)$↵
↵
$F(n+1)-\alphaF(n)=\beta(F(n)-\alphaF(n-1))$↵
↵
Let $G(n)=F(n+1)-\alphaF(n)$, also we have $G(n-1)=F(n)-\alphaF(n-1)$↵
↵
$G(n)=\betaG(n-1)$, therefore $G(n+1)=\betaG(n)$↵
↵
$G(n)=\beta^{n-1}G(1)$↵
↵
$F(n+1)-\alphaF(n)=\beta^{n-1}(F(2)-\alphaF(1))$ (1)↵
↵
--------------------------------↵
↵
Similarly, because of $F(n+1)=(\alpha+\beta)F(n)-\alpha\betaF(n-1)$ we have↵
↵
$F(n+1)-\betaF(n)=\alphaF(n)-\alpha\betaF(n-1)$↵
↵
$F(n+1)-\betaF(n)=\alpha(F(n)-\betaF(n-1))$↵
↵
Let $H(n)=F(n+1)-\betaF(n)$ we have $H(n-1)=F(n)-\betaF(n-1)$↵
↵
$H(n)=\alphaH(n-1)$, therefore $H(n+1)=\alphaH(n)$↵
↵
$H(n)=\alpha^{n-1}H(1)$↵
↵
$F(n+1)-\betaF(n)=\alpha^{n-1}(F(2)-\betaF(1))$ (2)↵
↵
--------------------------------↵
↵
Suppose that $\alpha\ne\beta$↵
↵
$(2)-(1)$ we have↵
↵
$(\alpha-\beta)F(n)=\alpha^{n-1}(F(2)-\betaF(1))-\beta^{n-1}(F(2)-\alphaF(1))$↵
↵
$F(n)=\frac{\alpha^{n-1}(F(2)-\beta F(1))-\beta^{n-1}(F(2)-\alpha F(1))}{\alpha-\beta}$↵
↵
--------------------------------↵
↵
How to get the proper $\alpha, \beta$?↵
↵
According to the Vieta Theorem, $\alpha, \beta$ is the two solutions of quadratic equation $x^2-ax-b=0$.↵
↵
Of course, we only talk about $\alpha\ne\beta, a^2\ne -4b$.↵
↵
Just solving the quadratic equation is OK. (You can get the formula for solving a quadratic equation from the problem [problem:530A].)↵
↵
This equation is called *the characteristic equation*.↵
↵
--------------------------------↵
↵
Example: Solve *the Fibonacci sequence* $F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)$.↵
↵
Solution: Here we have $\alpha=\frac{1-\sqrt5}{2}, \beta=\frac{1+\sqrt5}{2}$↵
↵
$$F(n)=\frac{\alpha^{n-1}(F(2)-\beta F(1))-\beta^{n-1}(F(2)-\alpha F(1))}{\alpha-\beta}↵
=\frac{(\frac{1-\sqrt5}{2})^{n-1}(1-\frac{1+\sqrt5}{2}\times 1)-(\frac{1+\sqrt5}{2})^{n-1}(1-\frac{1-\sqrt5}{2}\times 1)}{\frac{1-\sqrt5}{2}-\frac{1+\sqrt5}{2}}↵
=\frac{(\frac{1-\sqrt5}{2})^n-(\frac{1+\sqrt5}{2})^n}{-\sqrt5}=\frac{(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n}{\sqrt5}$$↵
↵
(because we have $1-\frac{1+\sqrt5}{2}=\frac{2-(1+\sqrt5)}{2}=\frac{1-\sqrt5}{2}, 1-\frac{1-\sqrt5}{2}=\frac{2-(1-\sqrt5)}{2}=\frac{1+\sqrt5}{2}$)↵
↵
-------------------------------↵
↵
What will happen if $\alpha=\beta$, $a^2=4b$?↵
↵
I am sorry that I cannot solve it yet.↵
↵
I'll try to solve it later.↵
↵
-------------------------------↵
↵
**UPD:** This method can be used to solve the recursions with lengths more than $2$.↵
↵
We replace the quadratic equation with an equation with higher degree, and do the same thing as quadratic.
↵
###### 1. Preliminary Knowledge↵
(1) The solution of recursion $F(n+1)=aF(n)$ is $F(n)=a^{n-1}F(1)$.↵
↵
(2) The solution of recursion $F(n+1)=F(n)+a$ is $F(n)=(n-1)a+F(1)$.↵
↵
(3) The recursion $F(n+1)=kF(n)$ is the same as $F(n)=kF(n-1)$, also $F(n+1)=aF(n)+bF(n-1)$ is the same as $F(n)=aF(n-1)+bF(n-2)$ in this blog.↵
↵
###### 2. Solving $F(n+1)=aF(n)+b$, $a, b$ are constants, $a>1$↵
**The main idea is to create another function G(n) that satisfy $G(n)=kG(n-1)$ with constant k, solve G(n), and then solve F(n).**↵
↵
$F(n+1)=aF(n)+b$↵
↵
$F(n+1)=aF(n)+\frac{ab-b}{a-1}$↵
↵
$F(n+1)=a(F(n)+\frac{b}{a-1})-\frac{b}{a-1}$↵
↵
$F(n+1)+\frac{b}{a-1}=a(F(n)+\frac{b}{a-1})$↵
↵
Let $G(n)=F(n)+\frac{b}{a-1}$ we have↵
↵
$G(n)=aG(n-1)$↵
↵
$G(n)=a^{n-1}G(1)$↵
↵
$F(n)+\frac{b}{a-1}=a^{n-1}(F(1)+\frac{b}{a-1})$↵
↵
$F(n)=a^{n-1}(F(1)+\frac{b}{a-1})-\frac{b}{a-1}$↵
↵
###### 3. Solving $F(n+1)=aF(n)+bF(n-1)$, $a, b$ are constants↵
**The main idea is also to create $G(n)$, but the method is different, and the function $G(n)$ is more complicated.**↵
↵
$F(n+1)=aF(n)+bF(n-1)$↵
↵
Let $\alpha, \beta$ be two real numbers that satisfy $\alpha+\beta=a, \alpha\beta=-b, \alpha\le\beta$ we have↵
↵
$F(n+1)=(\alpha+\beta)F(n)-\alpha\betaF(n-1)$↵
↵
$F(n+1)-\alphaF(n)=\betaF(n)-\alpha\betaF(n-1)$↵
↵
$F(n+1)-\alphaF(n)=\beta(F(n)-\alphaF(n-1))$↵
↵
Let $G(n)=F(n+1)-\alphaF(n)$, also we have $G(n-1)=F(n)-\alphaF(n-1)$↵
↵
$G(n)=\betaG(n-1)$, therefore $G(n+1)=\betaG(n)$↵
↵
$G(n)=\beta^{n-1}G(1)$↵
↵
$F(n+1)-\alphaF(n)=\beta^{n-1}(F(2)-\alphaF(1))$ (1)↵
↵
--------------------------------↵
↵
Similarly, because of $F(n+1)=(\alpha+\beta)F(n)-\alpha\betaF(n-1)$ we have↵
↵
$F(n+1)-\betaF(n)=\alphaF(n)-\alpha\betaF(n-1)$↵
↵
$F(n+1)-\betaF(n)=\alpha(F(n)-\betaF(n-1))$↵
↵
Let $H(n)=F(n+1)-\betaF(n)$ we have $H(n-1)=F(n)-\betaF(n-1)$↵
↵
$H(n)=\alphaH(n-1)$, therefore $H(n+1)=\alphaH(n)$↵
↵
$H(n)=\alpha^{n-1}H(1)$↵
↵
$F(n+1)-\betaF(n)=\alpha^{n-1}(F(2)-\betaF(1))$ (2)↵
↵
--------------------------------↵
↵
Suppose that $\alpha\ne\beta$↵
↵
$(2)-(1)$ we have↵
↵
$(\alpha-\beta)F(n)=\alpha^{n-1}(F(2)-\betaF(1))-\beta^{n-1}(F(2)-\alphaF(1))$↵
↵
$F(n)=\frac{\alpha^{n-1}(F(2)-\beta F(1))-\beta^{n-1}(F(2)-\alpha F(1))}{\alpha-\beta}$↵
↵
--------------------------------↵
↵
How to get the proper $\alpha, \beta$?↵
↵
According to the Vieta Theorem, $\alpha, \beta$ is the two solutions of quadratic equation $x^2-ax-b=0$.↵
↵
Of course, we only talk about $\alpha\ne\beta, a^2\ne -4b$.↵
↵
Just solving the quadratic equation is OK. (You can get the formula for solving a quadratic equation from the problem [problem:530A].)↵
↵
This equation is called *the characteristic equation*.↵
↵
--------------------------------↵
↵
Example: Solve *the Fibonacci sequence* $F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)$.↵
↵
Solution: Here we have $\alpha=\frac{1-\sqrt5}{2}, \beta=\frac{1+\sqrt5}{2}$↵
↵
$$F(n)=\frac{\alpha^{n-1}(F(2)-\beta F(1))-\beta^{n-1}(F(2)-\alpha F(1))}{\alpha-\beta}↵
=\frac{(\frac{1-\sqrt5}{2})^{n-1}(1-\frac{1+\sqrt5}{2}\times 1)-(\frac{1+\sqrt5}{2})^{n-1}(1-\frac{1-\sqrt5}{2}\times 1)}{\frac{1-\sqrt5}{2}-\frac{1+\sqrt5}{2}}↵
=\frac{(\frac{1-\sqrt5}{2})^n-(\frac{1+\sqrt5}{2})^n}{-\sqrt5}=\frac{(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n}{\sqrt5}$$↵
↵
(because we have $1-\frac{1+\sqrt5}{2}=\frac{2-(1+\sqrt5)}{2}=\frac{1-\sqrt5}{2}, 1-\frac{1-\sqrt5}{2}=\frac{2-(1-\sqrt5)}{2}=\frac{1+\sqrt5}{2}$)↵
↵
-------------------------------↵
↵
What will happen if $\alpha=\beta$, $a^2=4b$?↵
↵
I am sorry that I cannot solve it yet.↵
↵
I'll try to solve it later.↵
↵
-------------------------------↵
↵
**UPD:** This method can be used to solve the recursions with lengths more than $2$.↵
↵
We replace the quadratic equation with an equation with higher degree, and do the same thing as quadratic.
