Mathematical Induction --- $a_n=2a_{n-1}-1$

Question

Problem

Finish the following mathematical induction showing that $a_0 = 2$ and $a_n = 2a_{n-1}-1$ implies $a_n = 2^n +1$.

Basis: Prove that $a_0 = 2^0 + 1$

Proof:

$a_0$ = $________$ = $________$ = $2^0 + 1$

Induction:

Assume $k \ge 0$ and $a_k = 2^k +1$

Want to show that $a_{k+1} = 2^{k+1} + 1$

In the induction proof, use $a_{k+1} = 2a_k - 1$

Also use $2^{k+1}$ and $2*2^k$.

Proof:

$k\ge0$ and $a_k = 2^k + 1$ and $a_{k+1} = 2a_k - 1$ implies:

$a_{k+1}$ = $________$ = $________$ = $________$ = $2^{k+1} + 1$

Attempt @ Solution

I have not attempted to solve this, because I don't know where to begin. In plain-english, what is the problem asking for, and what is an outline of steps I need to do to find a solution to this problem? I'm not asking for the problem to be solved. I don't even understand what the problem is asking for.

Answer 1

(As a commenter points out, all you need to do to solve the problem is fill in the blanks. But it seems like you may have a bit of confusion about induction, so I will try and explain that).

Induction is a method of proof for the natural numbers. Specifically, say you have a subset $X \subseteq \mathbb{N}$ then if you can show that $0 \in X$ and if $n \in X$ then $n +1 \in X$ then you know $X$ is all the natural numbers, i.e. $X = \mathbb{N}$.

In your problem, your $X$ is

$$X = \{ n \in \mathbb{N} \mid a_n = 2^n +1 \}$$.

So first, we have to show that $0 \in X$. What does this mean? This means that we want to show $a_0 = 2^0 + 1$. (You are given $a_0 = 2$).

Next, to prove $n \in X \rightarrow n+1 \in X$ we assume that $n \in X$ in other words, $a_n = 2^n+1$. Now we want to show, using this assumption, that $a_{n+1} = 2^{n+1}+1$.

Then, once we have shown this, by induction we know that $X =\mathbb{N}$, which means that $a_n = 2^n +1$ for all $n \in \mathbb{N}$.

Some intuition: One way to think of induction is like a line of dominoes falling over. If you set up a bunch of dominoes all you have to do is push the first one over, and make sure that each domino can reach the next in the line. Then you "know" the whole line will fall over.