Given recursive formula $a_n = 2a_{n-1}+1$, show $a_n = 2^n -1$

Question

I came across a recursion homework problem for a graduate algorithms class while looking at recursive algorithms.

We are given a recursive formula for a recursive algorithm that gives the total number of moves at the $n^{\text{th}}$ recursion based on the $(n-1)^{\text{st}}$ recursion: $$ a_n = 2a_{n-1} + 1, $$ where $a_1 = 1$ and $a_2 = 3$.

How do we show that the final explicit formula is $a_n = 2^n - 1$?

Answer 1

You could show $a_n=2^n-1$ by mathematical induction. Base case: $a_1=1=2^1-1.$

Now assume $a_n=2^n-1.$ Then $a_{n+1}=2a_n+1=2(2^n-1)+1=2^{n+1}-2+1=2^{n+1}-1$.

QED

Answer 2

$a_n=2a_{n-1}+1$

1.Characteristic equation

$b_n:=a_n+1$

$b_n-2b_{n-1}=0$

The characteristic equation is now $x-2=0$

So $b_n=2^nA \ \ \ a_n=2^nA-1$ and A is 1 from initial conditions

How to get the characteristic equation?

2.Simple manipulation

Divide by $2^n$ on both sides

$$\frac{a_n}{2^n}-\frac{a_{n-1}}{2^{n-1}}=\frac{1}{2^n}$$

Now add equations for n,n-1,n-2 and so on to get

$$\frac{a_n}{2^n}-\frac{a_1}{2}=\sum{\frac{1}{2^r}}=\frac{2^{n-1}-1}{2^n}$$

Answer 3

Unfortunately I did not know two other answers had been posted while I was typing out this answer, so here is my answer:

The obviously easier method which is to look at the pattern (or the formula given to prove), check its validity for $a_1 = 1$ and $a_2 = 3$ and assume it to be true for $a_n$ and prove it for $a_{n+1}$ like such:

Assuming $a_n = 2^n + 1$, multiply this by $2$ to get $2a_n = 2^{n+1} - 2$ but $a_{n+1} = 2a_n + 1 \implies a_{n+1} = 2^{n+1} - 2 + 1 = 2^{n+1} - 1$

Thus if the formula is valid for $1,2$ and assuming it to be valid for $n$, we proved it to be valid for $n+1$, put $n = 2$ to get it is valid for $3$ and $n = 3$ to get it is valid for $4$ and so on (this is also called principle of mathematical induction)

Now for the better method, I only get one method in mind to prove it without assuming anything which is as follows:

\begin{align} a_1 &= 1 \tag1\label1 \\ a_2 &= 2a_1 + 1 \tag2\label2 \\ a_3 &= 2a_2 + 1 \tag3\label3 \\ \vdots & \\ a_n &= 2a_{n-1} + 1 \tag{$n$}\label{n} \end{align}

Multiply equation $r$ by $2^{n-r}$ and add all equations from \eqref{1} to \eqref{n} and see that equation $r$ + equation $r+1$ gives $2^{n-r-1}a_{r+1} = 2^{n-r-1} + 2^{n-r}$ and following through this "chain reaction" of equations, we get $a_n = 1 + 2 + 4 + \dots + 2^{n-1}$

$\therefore a_n = 1 + 2 + 4 + \dots + 2^{n-1} \tag{$n+1$}\label{n+1}$

multiplying this equation by $2$ to get:

$2a_n = 2 + 4 + 8 + \dots + 2^n \tag{$n+2$}\label{n+2}$

equation \eqref{n+2} - equation \eqref{n+1} gives $a_n = 2^n - 1$ (all middle terms $2, 4, 8$ cancel out).

This proves the formula $a_n = 2^n - 1$

Answer 4

My approach was somewhat different from the three approaches above. Even though the question has been thoroughly answered, I'd like to share it anyway.

Consider that if $a_n = 2a_{n-1} + 1$, then $a_{n-1} = 2a_{n-2} + 1$.

It can be concluded that $a_n - a_{n-1} = 2(a_{n-1} - a_{n-2})$ since:

\begin{aligned} a_n - a_{n-1} &= (2a_{n-1} + 1) - (2a_{n-2} + 1) \\ &= 2a_{n-1} + 1 - 2a_{n-2} -1 \\ &= 2a_{n-1} - 2a_{n-2} \\ &= 2(a_{n-1} - a_{n-2}) \end{aligned}

This represents a property of exponential functions; each successive difference is double the last. Therefore, the relationship should be akin to an exponential with a base of $2$.

Let $f(n) = 2^{n} - k$. The above property of the recursive relationship can be demonstrated by determining the difference between $f(n)$ and $f(n-1)$:

\begin{aligned} f(n) - f(n - 1) &= (2^n - k) - (2^{n-1} - k) \\ &= 2^n - k - 2^{n-1} - k \\ &= 2^n - 2^{n-1} \\ &= 2^n - 2^{n-1} \\ &= 2(2^{n-1} - 2^{n-2}) \\ &= 2(f(n-1) - f(n-2)) \end{aligned}

showing that $f(n)$ satisfies the recursive sequence and that $a_n = f(n)$.

To determine the value of $k$, use the initial condition given in the problem (only one is necessary, so say $a_1 = f(1) = 1$) and solve for $k$: \begin{aligned} f(1) &= 1 \\ 2^1 - k &= 1 \\ 2 - k &= 1 \\ k &= 1 \\ \end{aligned}

Therefore, $a_n = f(n) = 2^n - 1$.

Answer 5

Let $A(z)=\sum_{n \ge 1} a_n z^n$ be the ordinary generating function. The recurrence implies that $$\sum_{n \ge 2} a_n z^n = \sum_{n \ge 2} (2a_{n-1}+1) z^n$$ Equivalently, $$A(z) - a_1 z = 2z \sum_{n \ge 2} a_{n-1} z^{n-1} + \sum_{n \ge 2} z^n = 2z A(z)+\frac{z^2}{1-z}$$ Solving for $A(z)$ yields $$A(z) = \frac{a_1 z+z^2/(1-z)}{1-2z} = \frac{z}{(1-2z)(1-z)} = \frac{1}{1-2z} - \frac{1}{1-z} = \sum_{n \ge 0}(2^n-1) z^n,$$ which immediately implies that $a_n=2^n-1$.

Answer 6

Other answers have already given how to do it in a standard way by solving characteristic equation or using induction hypothesis... But if you believe in math for fun, you may want to follow along... :)

---

Let $f(x)=2x+1$.

Notice that:

$$a(n)=\underbrace{f\circ f \circ\ldots\circ f}_{\text{$n$ times}}(0)$$

Applying $f$ on a whole number is same as appending a $1$ to the end of its binary form.

$f^{n}(0)$ is same as appending $n$ $1$'s to end of $0$.

$$f^{n}(0) = \underbrace{{11\ldots 1}}_{\text{$n$ times}}$$

What happens if you add a $1$ to this value? You will end up with $1$ followed by $n$ zeroes $0$ which is precisely $2^n$. $$\therefore f^n(0)=2^n-1$$

---

For the sake of variety, I will also add a wild approach which is akin cracking a nut with sledge hammer. :)

Consider the linear transformation $(x,y)\mapsto (2x+y, y)$ over $\mathbb R^2$. Its matrix is given by: $\mathscr A =\begin{pmatrix}2 & 1\\ 0 &1\end{pmatrix}\tag*{}$ Clearly, $\begin{pmatrix}f(x)\\ 1\end{pmatrix}=\mathscr A\begin{pmatrix}x\\ 1\end{pmatrix}\tag*{}$ and $\begin{pmatrix}f^n(x)\\ 1\end{pmatrix}=\mathscr A^n\begin{pmatrix}x\\ 1\end{pmatrix}\tag*{}$

Since, $\mathscr A$ is upper triangular, it’s immediately clear that its eigenvalues are $2$ and $1$. Now, find the corresponding eigenvectors $(-1, 1)$ and $(1,0)$ respectively in order to diagonalize $\mathscr A$. $\mathscr A=\begin{pmatrix} -1 & 1\\ 1 & 0\end{pmatrix} \begin{pmatrix} 2 & 0\\ 0 & 1\end{pmatrix} \begin{pmatrix} -1 & 1\\ 1 & 0\end{pmatrix}^{-1}\tag*{}$ Now raise it to the power of $n$, $\begin{align}\mathscr A^n &=\begin{pmatrix} -1 & 1\\ 1 & 0\end{pmatrix} \begin{pmatrix} 2^n & 0\\ 0 & 1\end{pmatrix} \begin{pmatrix} -1 & 1\\ 1 & 0\end{pmatrix}^{-1}\\ &= \begin{pmatrix} 2^n & 2^n-1\\ 0 & 1\end{pmatrix} \end{align}\tag*{}$ Thus, $\begin{pmatrix}f^n(x)\\ 1\end{pmatrix}=\begin{pmatrix} 2^n & 2^n-1\\ 0 & 1\end{pmatrix} \begin{pmatrix}x\\ 1\end{pmatrix}\tag*{}$

Now just substitute $x=0$.