Finding explicit formula Find an explicit formula for $a_k$ if $a_0=0$ and $a_{k+1}=a_k+2^k$ for $k\geq 0$.
Thanks much for the help!
 A: HINT: Always begin by collecting some data, unless the computations are impossibly hard. By easy calculation you should find these values:
$$\begin{array}{rcc}
k:&0&1&2&3&4&5\\
a_k:&0&1&3&7&15&31
\end{array}$$
The numbers $a_k$ should be very recognizable and should immediately suggest a closed form for $a_k$. Once you have that, prove it by induction on $k$.
A: Hint:
Compute the first few values of $a_k$. Can you guess an explicit formula?
A: Write down some of the first elements to get a hint:
$0,1,3,7,15,...$
A: The first 11 values are 

{0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047}

This cries to be $2^k -1$ doesn't it? Now you just need to prove it.
A: So
$$\begin{align}
a_k =& a_{k-1} + 2^{k-1} \\ &=  a_{k-2} + 2^{k-2}+2^{k-1} \\ &= a_{k-3} +2^{k-3} + 2^{k-2} + 2^{k-1} \\ &= \dots \\
&= a_0 + 2^0 + 2^1 + 2^2 + \dots + 2^{k-2} + 2^{k-1} \\
&= 1 + 2^1 + 2^2 + \dots + 2^{k-2} + 2^{k-1}
\end{align}
$$
What do you end up with?
A: Let $F(x)=\sum_{k\geq 0}a_k x_k$.  Then multiply the recursive formula by $x^{k+1}$ and summing over all $k\in \mathbb{N}$:
$$\sum_{k\geq0}a_{k+1}x^{k+1}=\sum_{k\geq0}a_kx^{k+1}+x\sum_{k\geq0}(2x)^k$$
$$\therefore F(x)=xF(x)+\frac{x}{1-2x}\\F(x)=\frac{x}{(1-x)(1-2x)}=x(1+x+x^2+\cdots+)(1+2x+4x^2+\cdots)$$
$$\therefore a_k=\sum^{k-1}_{i=0}2^i=\boxed{2^k-1}$$
