How to solve this reccurence relation?

Question

Let a,b,c be real numbers. Find the explicit formula for $f_n=af_{n-1}+b$ for $n \ge 1$ and $f_0 = c$

So I rewrote it as $f_n-af_{n-1}-b=0$ which gives the characteristic equation as $x^2-ax-b=0$. The quadratic formula gives roots $x= \frac{a+\sqrt{a^2+4b}}{-2}, \frac{a-\sqrt{a^2+4b}}{-2}$

Then $f_n=P_1(\frac{a+\sqrt{a^2+4b}}{-2})^n+P_2(\frac{a-\sqrt{a^2+4b}}{-2})^n$ and using the initial condition $t_0=c$ gives $C=P_1+P_2 \Rightarrow P_1=C-P_2$

So $(C-P_2)(\frac{a+\sqrt{a^2+4b}}{-2})^n+P_2(\frac{a-\sqrt{a^2+4b}}{-2})^n$ what next? I tried expanding but that didn't help. I know the answer is something like $cd^n-\frac{b}{a-1}+\frac{bd^n}{a-1}$

Answer 1

If $a=1$, then $f_n=f_0+nb$, otherwise since $f_n=af_{n-1}+b$ we can subtract $\frac{b}{1-a}$ from both sides to get $$ f_n-\frac{b}{1-a}=a\left(f_{n-1}-\frac{b}{1-a}\right) $$ therefore, $$ \begin{align} f_n &=\frac{b}{1-a}+a^n\left(f_0-\frac{b}{1-a}\right)\\ &=a^nf_0+b\frac{1-a^n}{1-a} \end{align} $$

Answer 2

Why not consider this?

$f_n + m = a(f_{n-1} + m) \Longrightarrow (a-1)m=b$

1) $a=1$, simple recurrence $f_n = f_{n-1} + b$, $f_n = bn+c$

2) $a\neq 1$, $m=\frac{b}{a-1}$, $f_n+m = a(f_{n-1}+m)$, geometric sequence $f_n+m=a^n(c+m)$

Hope it is helpful!

Answer 3

In fact, your approach is false. Your characteristic polynomial would work for the recurrence relation $f_{n+1}=af_n+bf_{n-1}$, but not for your case. You need to have a homogeneous relation for working with that polynomial, which you don't. Therefore, you need first to do a couple modifocations.

You can write $$ f_{n+2} - f_{n+1 }=a(f_{n+1} - f_{n}),$$ which gives immediately a homogenous version (and now we can use characteristic polynomial!): $$f_{n+2} = (1+a)f_{n+1 } - af_{n}$$ with a characteristic polynomial $x^2-(1+a)x+a$, its roots are $1$ and $a$.

Suppose that $a\ne 1$, hence, you have $f_n=p_1a^n+p_2$. Now we need to check that the initial relation (non-homogenous): $$p_1a^{n+1}+p_2=a(p_1a^{n}+p_2)+b,$$ which gives us $p_2=\frac{b}{1-a}$. Now, the initial condition at $n=0$ allows to say that $p_1=c-p_2=c-\frac{b}{1-a}$. We rewrite to get $$f_n =\left(c-\frac{b}{1-a}\right)a^n+\frac{b}{1-a}.$$

Now on to the case $a=1$. In this case the roots of characteristic polynomial are the same, therefore the solutions are $f_n = p_1na^n+p_2 a^n=p_1n+p_2 $. The initial condition gives immediately $p_2=c$. We check the non-homogenous relation: $$p_1(n+1)+c = (p_1n+c)+b$$ or $$p_1 = b.$$ Thus, the solution is $$f_n = bn+c.$$