I'm trying to prove the following recurrence:
$g(n) = 3g(n-1) + 2$
$g(0) = 0$
$g(1) = 2$
$g(2) = 8$
...
I know that $g(n)$ in closed form is equal to $n^3 -1$, but I'm having a hard time proving it by induction. Here's what I've done so far:
$g(n) = 3[g(n-1)] + 2 = 3[(n -1)^3 -1] + 2 = 3(n - 1)^3 -1$
After the last step I get stuck, since clearly $3(n-1)^3$ is not equal to $n^3$.
Any help is greatly appreciated.
On
Another way: rewrite the equation as $a_{k+1}-a_{k}=\Delta a_{k+1}$
$$
\Bigg\{
\begin{array}{lr}
a_{k}=3 a_{k-1} +2\\
a_{k+1}=3 a_k+2
\end{array}
$$
Subtract the first equation from the second to get
$$
\Delta a_{k+1}=3 \Delta a_{k}=\ldots 3^n \Delta a_1
$$
Now sum both sides over $k$ to get
$$
a_{k}=3^k-1
$$
If $g(n)=3^n-1$ then we get recurrence
$$g(n+1)=3^{n+1}-1=3\cdot3^n-3+2=3(3^n-1)+2=3g(n)+2$$ your assumption $g(n)=n^3-1$ is wrong