How to solve nonhomgenous recurrence relation?

Question

I'm studying this topic in advance and I'm working on textbook problems. The problem is simple :

Solve the following recurrence relation

a) $a(n+1)-a(n)=2n+3$, $n$ is greater than or equal to $0$ and $a(0)=1$

b) $a(n+1)-a(n)=3n^2-n$, $n$ is greater than or equal to $0$ and $a(0)=3$

The answer in the back of the text says:

a) $a(n)=(n+1)^2$, $n$ greater than or equal to $0$

b) $a(n)=3+n(n-1)^2$, $n$ greater than or equal to $0$

I'm new to this topic and I want to know a efficient way to solve this problem. It is also good if you explain only one of them but step by step explanation to answer would be very much appreciated.

Answer 1

Recurrences of the form $$ a_{n+1} = a_n + f(n) $$ are so common that they have a specialized notation, namely $$ a_n = a_0 + \sum_{k=0}^{n-1} f(k) $$

Note that this is not a solution, merely a different notation for the same problem -- if you write out the formal meaning of what the $\sum$ notation stands for, you get exactly the original recurrence back.

However, you probably already know some techniques for dealing with finite sum; for example the first one $$ a_n = 1 + \sum_{k=0}^{n-1} 2k + 3 $$ is just the sum of a finite arithmetic sequence, which equals the number of terms times the average of the first and last term (Gauss's trick), so we get $$ a_n = 1 + n\frac{2\cdot 0 + 3 + 2(n-1) + 3}{2} = n^2 + 2n + 1$$ which you may be able to recognize as the square of $n+1$.

---

In the second recurrence you have $g(n)=\sum_k f(k)$ where $f$ is a second-degree polynomial. What I do with such things is to remember that $g$ in that case is always a polynomial one degree higher, and then I find its coefficients by expanding $g(n+1)=g(n)+f(n)$, simplifying, and then equating terms of the same degree in $n$.

Somewhere there's probably a nice canned formula that allows one to compute the coefficients of $g$ directly from those of $f$, but I don't care to go around remembering it -- it's not that often I have to sum polynomial progressions.

Answer 2

Here is a general technique for linear recurrence relations. You start by solving the homogeneous equation

$$ a(n+1)-a(n) = 0 $$

by assuming $a(n)=r^n$ and plugging back in the above equation which gives the characteristic equation

$$ r-1=0 \implies r=1 $$

which yields the solution $a_h(n)=c_1$.

The second step is to find a particular solution for the equation

$$ a(n+1)-a(n) = 2n+3 \longrightarrow (2)$$

by assuming

$$ a_p(n)= An^2+Bn+C $$

and plugging back in $(2)$ to determine the constants $A,B,C$ to get

$$ a_p(n) = n^2+2n. $$

So the general solution is given by

$$ a(n) = a_h(n) + a_p(n) = c_1 + n^2+2n. $$

To determine $c_1$ we exploit the initial condition $a(0)=1$ to get the final answer

$$ a(n)=1+2n+n^2 = (n+1)^2. $$

Answer 3

Given $$ a(n+1)-a(n)=f(n)\tag{1} $$ we can sum $(1)$ and get a telescoping series $$ \begin{align} \sum_{k=0}^{n-1}f(k) &=\sum_{k=0}^{n-1}[a(k+1)-a(k)]\\ &=\sum_{k=1}^na(k)-\sum_{k=0}^{n-1}a(k)\\ &=a(n)+\sum_{k=1}^{n-1}a(k)-\sum_{k=1}^{n-1}a(k)-a_0\\[9pt] &=a(n)-a(0)\tag{2} \end{align} $$ This sum is called a telescoping series because $$ \begin{align} &\sum_{k=0}^{n-1}[a(k+1)-a(k)]\\ &=[a_n\overbrace{-a_{n-1}]+[a_{n-1}}^{\text{cancel}}\overbrace{-a_{n-2}]+[a_{n-2}}^{\text{cancel}}\overbrace{-a_{n-3}]+\dots+[a_2}^{\text{cancel ... cancel}}\overbrace{-a_1]+[a_1}^{\text{cancel}}-a_0]\\[9pt] &=a_n-a_0\tag{3} \end{align} $$ That is, the paired adjacent terms cancel and the whole sum collapses, just like a telescope being put away.

Equation $(2)$ says $$ a_n=a_0+\sum_{k=0}^{n-1}f(k)\tag{4} $$ Thus, if we know how to sum $f(k)$, then we can solve $(1)$.

There are many posts showing how to sum polynomials, so I will just quote a few: $$ \begin{align} \sum_{k=0}^{n-1}1&=n\\ \sum_{k=0}^{n-1}k&=\frac{n(n-1)}2\\ \sum_{k=0}^{n-1}k^2&=\frac{(2n-1)(n-1)n}6\\ \end{align}\tag{5} $$ Equations $(4)$ and $(5)$ should enable you to solve the problems you are given.