I was given this exercise as a practice for discrete mathematics, among some others. The instruction is to provide a closed-form formula for the recursive formula shown below.
$u_n =2 + \sum_{i=1}^s 2^t*u_i $
where $s=n-1$ and $t=n-2i$.
We are asked to prove the closed-formed formula we suggested by induction. I have encountered trouble in my efforts, since, though I can prove my formula is true for a base case, and then assume it is true for k, I can't seem to prove it's true for k+1. We are told (a) $u_n$ is true for all n>1, (b) $u_1=2$
By evauluation,
$u_2= 2 + 1*2 = 4$ and $u_3 = 2+2^*u_1+\frac12*u_2=2+2*2+\frac12*4=6+2=8$
Being $u_1=2$
$u_2 = 4$
$u_3=8$
I suggested the formula
$u_n=2^n$, so that
$$u_n =2 + \sum_{i=1}^s 2^t*u_i =2^n$$
As I said, I failed to prove this by induction. Is anybody out there able to point my error out, or show how can I prove this by induction?
Suppose $u_i = 2^i$ for $i = 1, \ldots, n-1$, then
$$u_n = 2 + \sum_{i=1}^{n-1} 2^{n-2i} u_i = 2 + \sum_{i=1}^{n-1} 2^{n-2i} 2^i = 2 + \sum_{i=1}^{n-1} 2^{n-i} =$$
$$ =2+\sum_{j=1}^{n-1}2^j = 2 + \frac{1-2^n}{1-2} - 1 = 2^n$$