Finding a closed form solution

Question

For the sequence 0 2 8 34 144 ...

The recurrence relation is: $$\begin{align*} E(n) = 4*E(n-1)+E(n-2) \end{align*}$$

How to calculate the closed form expression for the following summation. $$\begin{align*} S(n) = \sum_{i=0}^nE_i \end{align*}$$

Answer 1

This is a second-order linear recurrence. The auxillary quadratic here is $$\lambda^2 = 4\lambda + 1,$$ so you have $$\lambda^2 - 4\lambda - 1 = 0.$$ Using the quadratic formula you get the bases $$\lambda = {4\pm \sqrt{16 + 4}\over 2} = 2\pm \sqrt{5}. $$ Your solution is of the form $$E(n) = c_0(2 -\sqrt{5})^n + c_1(2 + \sqrt{5})^n.$$ Match the initial conditions to ferret out the constants.

Answer 2

In addition to @ncmathsadist, hoping, this isn't homework

$\sum _{i=1}^n \left(\frac{\left(2-\sqrt{5}\right)^i}{2 \sqrt{5}}-\frac{\left(\sqrt{5}+2\right)^i}{2 \sqrt{5}}\right)=-\frac{\sqrt{5} \left(2-\sqrt{5}\right)^n-3 \left(2-\sqrt{5}\right)^n+\sqrt{5} \left(\sqrt{5}+2\right)^n+3 \left(\sqrt{5}+2\right)^n-2 \sqrt{5}}{2 \sqrt{5} \left(\sqrt{5}-1\right) \left(\sqrt{5}+1\right)}$