How to show that two recursive formulas are the same?

Question

Please see edit at the bottom of this post.

I need some help. I do not really understand what I am supposed to do. Does it suffice to list some of the numbers produced by the recursive formulas and compare them?

Show that the number sequence that are defined by the recursive formula $$a_n = 2a_{n-1}-1, n = 1,2,...$$ when $a_0 = 2$ is the same number sequence that are defined by $$a_n = 2^n + 1, n=0,1,... $$

How do I show $a_0$ when $a_n =2a_{n-1}-1, n = 1,2,...$?

I tried $a_0 = 2a_{0-1}-1 = 2a_{-1}-1$ and used that $a_1 = 2^{-1} + 1$ to get $a_0 = 2(2^{-1}+1)-1 = 2^0 + 2 - 1 = 2$. This cannot be allowed due to the fact that I used $n=0$ when it say that $n=1,2,...$

I would be really grateful if someone could help me. Thanks.

Edit: Am I allowed to rewrite the question like the following:

Given that $a_{n+1} = 2a_{(n+1)-1} -1 = 2a_{n} - 1$ and $a_{0} = 2$ then $a_{n} = 2^{n}+1$? Because that looks very similar to the induction exercises I have already done?

Answer 1

Rewrite second sequence as:

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

and check if first terms are equal (they are).

Answer 2

Hint:

$a_n=2^n+1 \quad \Rightarrow \quad a_0=2$ and: $ a_{n-1}=2^{n-1}+1 $ So: $$ 2a_{n-1}-1=2\cdot 2^{n-1}+2-1=2^n+1=a_n $$

Answer 3

I am not sure if your are familiar with principle of Mathematical Induction.

According to your question you should show that the two sequences $$\{2, 2a_{n-1}-1 ; n=1,2,... \}$$ and $$\{ 2^n+1; n=0,1,2,... \}$$ are equal.

To show that these two sequences are equal you should show that every term of the first one is equal to its corresponding term in the second one. Use principle of Mathematical induction to do that.

So for $n=0$, the corresponding term in the first sequence is $2$, and the corresponding term in the second sequence is $2^0+1=1+1=2$, so they are equal.

Now suppose equality holds for terms up to $n-1$, you should show it to terms of index $n$. Indeed, we have the $n$th term of the first sequence is $2a_{n-1}-1 $ and the $n$th terms of the second sequence is $2^n+1$. Note that the $n-1$th terms of both sequences are equal by the induction assumption, so $a_{n-1} =2^{n-1}+1 $, thus $2a_{n-1}-1 =2(2^{n-1}+1)-1 = 2^{n} +2-1=2^{n} +1$. Hence equality holds.

Answer 4

General case:

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

$$\begin{align} & =2(2a_{n-2}-1)-1 \\ & =4a_{n-2}-3 \\ & =4(2a_{n-3}-1)-3 \\ & =8a_{n-3}-7 \\ & =16a_{n-4}-15 \\ & \qquad\vdots \\ & =2^na_0-2^n+1?\tag{assumptions} \\ & =2^n(a_0-1)+1 \end{align}$$

We want to prove our assumed general form with induction:

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

$$a_0=2^0(a_0-1)+1$$

It holds for $a_0$, and if it holds for $a_{n-1}$, it holds for $a_n$.

Answer 5

I will answer my own question (if my answer is wrong please tell me).

Given that $a_{n+1} = 2a_{(n+1)-1} -1 = 2a_{n} - 1$ and $a_{0} = 2$ then $a_{n} = 2^{n}+1$ and $n=0,1,2...$.

Base case:

We have that $a_0 = 2$ and $a_0 = 2^0+1 = 2$

Inductive step:

Assume that it is true for $a_{k} = 2^{k}+1$. Then,

$a_{k+1} = 2a_{k} - 1\Rightarrow a_{k+1} =2(2^{k}+1)-1 = (2^{k+1} + 2) - 1 = 2^{k+1} + 1$. Q.E.D.