# How to show that two recursive formulas are the same?

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?

• Are you familiar with proofs by induction? If that is the case you only need to first prove that $a_0=b_0$ and then assuming $a_n=b_n$ to prove that $a_{n+1}=b_{n+1}$.
– wece
Oct 6 '16 at 13:40

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$$

• Thank you. I have a question. Am I allowed to rewrite the question like this: Given that $a_{n+1} = 2a_{(n+1)-1} -1 = 2a_{n} - 1$ and $a_{0} = 2$ then $a_{n} = 2^{n}+1$? Is this the same question as the question in my first post? Oct 6 '16 at 14:41
• yes, with $n$ starting from $0$ it is the same. Oct 6 '16 at 14:56

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).

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$.

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.

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...$.
We have that $a_0 = 2$ and $a_0 = 2^0+1 = 2$
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.