# 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!

-

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$.

-

Hint:

Compute the first few values of $a_k$. Can you guess an explicit formula?

-

Write down some of the first elements to get a hint: $0,1,3,7,15,...$

-

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.

-

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?

-

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}$$

-
You gave the complete answer away ... –  Thomas Mar 24 '13 at 20:49
oh derp myself... –  user67258 Mar 24 '13 at 20:52