Solving a recurrence relation. 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.
 A: 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)$.
A: 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$.
A: 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.
