3
$\begingroup$

Note: I am asking this question because I though my solution is interestingly easy and could solve for others with the same problem. If the solution is not completely correct, or incorrect, please feel free to correct it or improve it. I am sorry if this question has already been asked.

If we know that:

  • $a_0 = 0$

  • $\forall n \in N, a_{n + 1} = 2a_n + 1$

How do we prove by induction that $a_n = 2^n - 1$, $\forall n \in N$?

$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

This is my simple solution by induction:

Base:

$a_0 = 2^0 - 1 = 0$

Hypothesis:

Suppose $a_n = 2^n - 1$ is true for an arbitrary $n \in N$.

Inductive step:

Let's try to prove that also $a_{n+1} = 2^{n+1} - 1$ is also true.

We know that $a_{n + 1} = 2a_n + 1$, so I will replace $a_n$ with $2^n - 1$.

Now we have:

$a_{n + 1} = 2\cdot (2^n - 1) + 1$

$a_{n + 1} = (2^{n+1} - 2) + 1$

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

We have proved that if $a_n = 2^n - 1$, then follows $a_{n + 1} = (2^{n+1} - 1)$.

$\endgroup$

You must log in to answer this question.