$u_1=1, u_{n+1}=2u_n+1$, prove that $u_{n}=2^n-1$

Question

Prove that $u_{n}=2^{n}-1$ for all positive integers $n$, by induction or what means?

What I did was sub $u_{n}=2^{n}-1$ into the $u_{n+1}$, but that got me nowhere. so what options do i have now.

Answer 1

There are two methods you could use to solve this problem.

Method 1

Proof by induction:

Base case

First, we verify the base case where $n = 1$.

According to the sequence definition, $u_1 = 1$.

Now, let's check the formula $u_n = 2^n - 1$ for $u_1 = 1$:

$2^1 - 1 = 2 - 1 = 1$.

So the base case holds

Inductive step

Assume true for $n=k$ (where $k \in \mathbb{Z}^+$), so $u_k = 2^k - 1$.

When $n=k+1$ $$u_{k+1} = 2^{k+1} - 1$$

Remember that the recurrence relation $u_{k+1} = 2u_k + 1$.

Substituting the inductive hypothesis $u_k = 2^k - 1$ into the recurrence relation, we get:

$$u_{k+1} = 2(2^k - 1) + 1$$ $$= 2^{k+1} - 2 + 1$$ $$= 2^{k+1} - 1$$

Since $u_1$ was shown to be true and it was also shown that if the formula is true for $n=k$, $k \in \mathbb{Z}^+$, it is also true for $n=k+1$, it follows by the principle of mathematical induction that the formula is true for all $n \in \mathbb{Z}^+$

Method 2

We can also prove it by examining the pattern established by the recursive definition:

$$u_{n+1} = 2u_n +1$$

This implies that $$u_n = 2u_{n-1} + 1$$

Now let us try to derive an expression for $u_n$ in terms of earlier and earlier sequences until we spot a pattern $$u_n = 2u_{n-1} + 1$$ $$= 2(2u_{n-2}+1) + 1$$ $$= 2^2u_{n-2}+ 2 + 1$$ $$= 2^2(2u_{n-3}+1)+ 2 + 1$$ $$= 2^3u_{n-3}+ 2^2 + 2 + 1$$ $$\ldots$$ $$ = 2^ku_{n-k}+ 2^{k-1} + 2^{k-2} + \ldots + 1$$ $$ u_n = 2^ku_{n-k}+ \sum_{i=0}^{k-1} 2^k$$

Substituting $k=n-1$

$$ u_n = 2^{n-1}u_{n-(n-1)} + \sum_{i=0}^{(n-1)-1} 2^{i}$$ $$ = 2^{n-1}u_{n-n+1}+ \sum_{i=0}^{n-1-1} 2^{i}$$ $$ u_n= 2^{n-1}u_{1}+ \sum_{i=0}^{n-2} 2^{i}$$

$u_1 = 1$, so we can simplify the expression to

$$ u_n= 2^{n-1}+ \sum_{i=0}^{n-2} 2^{i} $$ $\label{E:1}$

$\sum_{i=0}^{n-2} 2^{i}$ is an geometric series with $u_1 = 1$ and $r = 2$.

We can substitue these valeus into the formula for the sum of a finite geometric sequence summation $$s_n = \frac{u_1(r^n - 1)}{r-1}$$ to find a simpler expression for $\sum_{i=0}^{n-2} 2^{i}$

It is important to note that $\sum_{i=0}^{n-2} 2^{i} = S_{n-1}$, not $S_{n-2}$ as there are $n-1$ terms since the summation starts from $i=0$

$$\sum_{i=0}^{n-2} 2^{i} = S_{n-1}$$ $$ = \frac{2^{n-1} - 1}{2-1}$$ $$ = \frac{2^{n-1} - 1}{1}$$ $$ = 2^{n-1} - 1$$ $$\sum_{i=0}^{n-2} 2^{i} = 2^{n-1} - 1$$

Substituting back into $u_n$: $$ u_n= 2^{n-1}u_{1}+ \sum_{i=0}^{n-2} 2^{i}$$ $$ = 2^{n-1}+ 2^{n-1} - 1$$ $$ = 2(2^{n-1})- 1$$ $$ u_n = 2^{n}- 1$$

I personally like method 2 more, as method 1 does involve some level of circular reasoning (i.e. using the result you are trying to show in your proof) which I don't really like