Explicit formula for $e_k = 4e_{k-1} + 5$

Question

The sequence looks like this:

$e_0 = 2$

$e_1 = 4(e_{1-1}) + 5 = 13$

$e_2 = 4(e_{2-1}) + 5 = 57$

$e_3 = 4(e_{3-1}) + 5 = 233$

$e_4 = 4(e_{4-1}) + 5 = 937$

How would I go about finding the explicit formula for this? For something a little simpler it's fairly easy to make a guess, and I've been told that 'guessing' is exactly how one is supposed to find the formula. However, I'm a little stumped on this.

Answer 1

A general approach to deal with recurring sequences of the form $$u_{n+1} = au_n +b$$

• if $a = 1$, it's an arithmetic progression.

• otherwise, let $r=\frac{b}{1-a}$. Consider $v_n = u_n -r$. we have $$ v_{n+1} = u_{n+1} - r = au_n+b - r = a(v_n + r) + b - r = a v_n $$ and $(v_n)_n$ is a geometric progression. You can then get the closed form for $v_n$, and $u_n = v_n + r$ will give you that of $u_n$.

Answer 2

Let $e_n=4^nu_n$, then $$ 4^{n}u_{n}=e_{n}=4e_{n-1}+5=4\cdot 4^{n-1}u_{n-1}+5=4^{n}u_{n-1}+5 $$ and thus $$ u_{n}=u_{n-1}+\frac{5}{4^{n}}=\left(u_{n-2}+\frac{5}{4^{n-1}}\right)+\frac{5}{4^{n}}=\cdots=u_0+\frac{5}{4}+\frac{5}{4^2}+\cdots+\frac{5}{4^{n}} \\ =u_0+\frac{5}{4}\left(1+\frac{1}{4}+\cdots+\frac{1}{4^{n-1}}\right)=u_0+\frac{5}{4}\left(\frac{1-\frac{1}{4^{n}}}{1-\frac{1}{4}}\right)=u_0+\frac{5}{3}\left(1-\frac{1}{4^n}\right) $$ and as $u_0=2$, $$ e_n=4^nu_{n}=2+\frac{5}{3}( 4^n-1) $$

Answer 3

$e_0 = 2$
$e_1 = 4e_0 + 5$
$e_2 = 4e_1 + 5=4^2e_0 + 4(5) + 5$
$e_3 = 4e_2 + 5=4^3e_0 + 4^2(5)+ 4^1(5) + 5= 4^3e_0+5(1 + 4^1 + 4^2 + 4^3)$

Now you should be able to guess that:

$e_k = 4^ke_0+5(1 + 4^1 + 4^2 + 4^3+...+4^{k-1})=4^ke_0 + \frac{5(4^k-1)}{3}$

and then you can prove that your "guess" is correct using induction.