Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 6 down vote accepted

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

share|cite|improve this answer


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

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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?

share|cite|improve this answer

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


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

share|cite|improve this answer
You gave the complete answer away ... – Thomas Mar 24 '13 at 20:49
oh derp myself... – user67258 Mar 24 '13 at 20:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.