About Solving Simple Recursions
Difference between en2 and en3, changed 0 character(s)
**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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English suncongbo 2019-09-11 14:36:22 233
en3 English suncongbo 2018-08-11 17:26:31 0 (published)
en2 English suncongbo 2018-08-09 13:09:43 32
en1 English suncongbo 2018-08-09 13:06:19 3662 Initial revision (saved to drafts)