Solving a recurrence relation.

Question

So I extracted this recurrence relation from a problem that I need to solve: $$ g(n) = 2g(n-1) + \sum_{i=0}^{n-2} g(i) + 1. $$ with $$ g(0) = 1. $$

All I know are two methods of linear homogenous relations, that not it.

Answer 1

There are several ways to approach this. You might notice that

$$\begin{align*} g(n)&=2g(n-1)+\sum_{i=0}^{n-2}g(i)+1\\ &=2g(n-1)+g(n-2)+\sum_{i=0}^{n-3}g(i)+1\\ &=2g(n-1)+\left(2g(n-2)+\sum_{i=0}^{n-3}g(i)+1\right)-g(n-2)\\ &=2g(n-1)+g(n-1)-g(n-2)\\ &=3g(n-1)-g(n-2)\;, \end{align*}$$

giving you a linear homogeneous recurrence.

Or you might begin by gathering some data; this is never a bad idea. Here are the first few values of $g(n$):

$$\begin{array}{rcc} n:&0&1&2&3&4&5\\ g(n):&1&3&8&21&55&144 \end{array}$$

Those number ought to be familiar: they’re all Fibonacci numbers. In fact, they’re alternate Fibonacci numbers:

$$\begin{array}{rcc} n:&0&1&2&3&4&5&6&7&8&9&10&11&12\\ F_n:&0&1&\underline1&2&\underline3&5&\underline8&13&\underline{21}&34&\underline{55}&89&\underline{144} \end{array}$$

This very strongly suggests that $g(n)=F_{2n+2}$. You could prove this by induction and then use the Binet formula to get a closed form for $g(n)$.

Answer 2

As shown in my answer to the preceding question, the recurrence relation can be written as

$$ \begin{pmatrix}g(n)\\X(n)\end{pmatrix} = A \begin{pmatrix}g(n-1)\\X(n-1)\end{pmatrix} $$ with $$ A = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}\quad\text{and}\quad X(0) = 1\text{.} $$

Then $$\begin{pmatrix}g(n)\\X(n)\end{pmatrix} = A^n \begin{pmatrix}g(0)\\X(0)\end{pmatrix} = A^n\begin{pmatrix}1\\1\end{pmatrix},$$ so the problem reduces to the computation of $A^n$. For this, diagonalize $A$.

Answer 3

Another way is to write the equation for $g(n-1)$:

$$ g(n-1) = 2 g(n-2) + \sum_{k=0}^{n-3} g(k) + 1 $$ and subtract it from $g(n)$ to get the linear equation: $g(n) = 3 g(n-1) - g(n-2)$ that can be solved using generating functions.