Recurrence Relation - how to derive a proper series

Question

I have a problem with understanding the way of deriving a series based on a given recurrence relation.

Let us consider the following recurrence relation: $$ f(n) = b + a f(n-1) $$ for some values $a$ and $b$.

My goal is to a find a general formula for $f(n)$. I suppose that I can do it using a series as follows $$ f(n) = b + a f(n-1) = b + a(b + a f(n-2)) = \ldots = \sum_{i=0}^{\infty} b a^i. $$

The second approach to this problem can be as follows: I write a recurence formula for $n+1$ element, i.e. $$ f(n+1) = b + a f(n) \Rightarrow f(n) = -\frac{b}{a} + \frac{1}{a} f(n+1) $$ and therefore $$ f(n) = -\frac{b}{a} + \frac{1}{a}f(n+1) = -\frac{b}{a} + \frac{1}{a} \left(-\frac{b}{a} + \frac{1}{a}f(n+2)\right) = \ldots = -\sum_{i=1}^{\infty}\frac{b}{a^i} $$

I obtained two different answers. I cannot understand which of these approaches is correct and why.

I suppose that this is a basic issue in mathematics, but I have never learn about it and I am just curious how to work with such recurence relations.

Answer 1

The first comes closer, but neither of them is correct, I’m afraid. For starters, there are infinitely many sequences satisfying the given recurrence, so you need to specify an initial value, say $f(0)$, to pin down which one of them you have. Then your summation is actually finite:

$$\begin{align*} f(n)&=b+af(n-1)\\ &=b+a\big(b+af(n-2)\big)\\ &=b+ab+a^2f(n-2)\\ &=b+a\big(b+ab+a^2f(n-3)\big)\\ &=b+ab+ab^2+a^3f(n-3)\\ &\;\;\vdots\\ &=b\sum_{i=0}^{k-1}a^i+a^kf(n-k)\\ &\;\;\vdots\\ &=b\sum_{i=0}^{n-1}a^i+a^nf(0)\\ &=\frac{b(a^n-1)}{a-1}+a^nf(0)\,, \end{align*}$$

Of course this doesn’t work if $a=1$, since the denominator of that last fraction is $0$, but in that case the recurrence is just $f(n)=b+f(n-1)$, and the calculation is

$$\begin{align*} f(n)&=b+f(n-1)\\ &=b+\big(b+f(n-2)\big)\\ &=2b+f(n-2)\\ &=2b+\big(b+f(n-3)\big)\\ &=3b+f(n-3)\\ &\;\;\vdots\\ &=kb+f(n-k)\\ &\;\;\vdots\\ &=nb+f(0)\,. \end{align*}$$

There are other ways to derive these closed forms, but this is the one that is closest to what you were trying to do.

Answer 2

We can consider in this way: Suppose we have some constant $c$ such that $$f(n)+c=af(n-1)+b+c=a[f(n-1)+c].$$Then it follows that $b+c=ac$, so $c=b/(a-1)$ provided $a\neq 1$. As a result, $$f(n)+\frac{b}{a-1}=af(n-1)+b+\frac{b}{a-1}=a\left[f(n-1)+\frac{b}{a-1}\right].$$ We then have $$f(n)+\frac{b}{a-1}=a^{n-1}\left[f(1)+\frac{b}{a-1}\right].$$That is, $$f(n)=a^{n-1}f(1)+\frac{a^{n-1}-1}{a-1}\cdot b.$$

If $a=1$, the case is even easier: $f(n)$ is an arithmetic progression. $$f(n)=f(1)+(n-1)b.$$

Answer 3

Your formulas can't be true because they do not depend on $n$. Indeed, in the first formula you will at some point end to $(b+af(0))$ which can't lead to further computation using the recursive formula. As for your second formula, indeed you will never stop because the index of $f(n)$ is always increasing, but you have to be careful when dealing with infinity. In your recursive formula, you always have a $f(n+p)$ at then end which then suddenly disappear when $n\rightarrow +\infty$ for some reasons. One way to obtain a formula for $f(n)$ is to write $$ (\star)\hspace{0.5cm}\ \frac{f(k+1)}{a^{k+1}}-\frac{f(k)}{a^k}=\frac{b}{a^k} $$ Summing this from $k=0$ to $k=n-1$ gives (I suppose $a\neq 1$ otherwise the result is straightforward) $$ \frac{f(n)}{a^n}-f(0)=\sum_{k=0}^{n-1}\frac{b}{a^k} $$ Therefore $$ f(n)=f(0)a^n+\sum_{k=0}^{n-1}ba^{n-k}=f(0)a^n+\sum_{k=1}^n ba^k $$ Letting $n\rightarrow +\infty$ gives your first formula $\displaystyle \lim\limits_{n\rightarrow +\infty}f(n)=\sum_{k=1}^{+\infty}ba^k$ (You only get the limit because in order continue an infinite amount of times your recursive formula you need to have "$n=+\infty$", this is a bit messy but it helps to understand where is your error). However, this only works if $a<1$ because of the infinite sum and the limit $\lim\limits_{n\rightarrow +\infty}f(0)a^n=0$. When $a>1$ this result does not work at all (in particular if $f(0)<0$ you can end up with a $\infty-\infty$ indeterminated form) but summing $(\star)$ from $k=n$ to $k=N-1$ gives $$ \frac{f(N)}{a^N}-\frac{f(n)}{a^n}=\sum_{k=n}^{N-1}\frac{b}{a^k} $$ Thus $$ f(n)=\frac{f(N)}{a^{N-n}}-\sum_{k=n}^{N-1}\frac{b}{a^{k-n}}=\frac{f(N)}{a^{N-n}}-\sum_{k=0}^{N-n-1}\frac{b}{a^k} $$ Letting $N\rightarrow +\infty$ leads to $\displaystyle f(n)=\lim\limits_{N\rightarrow +\infty}\frac{f(N)}{a^{n-N}}-\sum_{k=0}^{+\infty}\frac{b}{a^k}$. While the series converges because $a>1$, we do not know what happens for $\lim\limits_{N\rightarrow +\infty}\frac{f(N)}{a^{N-n}}$ (in fact we could know because we have a precise formula for $f(N)$). This is the error in your formula 2., $f(N)$ fades out with the dots and you are ignoring what happens with this $f(N)$, maybe it blows out or vanishes but you can't know without further study.

Answer 4

$$f(n)=a f(n-1)+b$$ substitute $n\to n+1$ $$f(n+1)=af(n)+b$$ Subtract the two relations $$f(n+1)-f(n)=af(n)-af(n-1)$$ reorder $$f(n+1)-(a+1)f(n)+af(n-1)=0$$ the equation characteristic is $$x^2-(a+1)x+a=0\to x_1=1;\;x_2=a$$ the general solution is $$f(n)=h+ka^n$$