How to prove the following.

Question

Let $\{_, _, _,\cdots \}$ be the sequence defined by the following recurrence relation:

• $_ = $

• $_ = \times _{−} +$ for $ ≥ $

How to prove $_ = ^{+} − $ for any integer $ ≥ $?

Can anyone please help to prove this as I have no idea about this.

Answer 1

I will show you how to get started on a proof by induction.

Base case: for $n=0$, we have $a_0=1$ by definition, and $2^{0+1}-1=1$.

Induction step: Suppose $a_k=2^{k+1}-1$ for some $k>0$. Then to complete the proof we wish to show that $a_{k+1}=2^{k+2}-1$.

Do you see how to finish the proof?

Answer 2

Either you do as lulu wrote in the comments and prove that $\{b_n\}$ defined by $b_n=2^{n+1}-1$ satisfy the condition for the sequence $\{a_n\}$. Here, you need that a sequence is uniquely determined by a recursion with an initial condition.

Or you prove it by induction.

For the induction step, you have to prove $$ a_n=2a_{n-1}-1=\ldots=2^{n+1}-1 $$

Answer 3

This is a way to prove it, but it's far easier to follow @lulu's comment, or @Mundron's hint.

Suppose $f(x)=\sum_{i=0}^{\infty}a_ix^i$, then $$\begin{align}f(x)=a_0+(2a_0+1)x+(2a_1+1)x^2+\dots\\f(x)=a_0+2xf(x)+\frac{1}{1-x}-1\\f(x)=2xf(x)+\frac{1}{1-x}\\f(x)(1-2x)=\frac{1}{1-x}\\f(x)=\frac{1}{(1-x)(1-2x)}=-\frac{1}{1-x}+\frac{2}{1-2x}\\f(x)=\sum_{i=0}^{\infty}(-1)x^i+\sum_{i=0}^{\infty}2^{i+1}x^i\end{align}$$

Comparing the coefficients of $f(x)=\sum_{i=0}^{\infty}a_ix^i$ with $f(x)=\sum_{i=0}^{\infty}\left (-1+2^{i+1}\right )x^i$ we conclude that $$a_n=2^{n+1}-1$$

Answer 4

Alt. hint:   rewrite it in the following form, then telescope:

$$ a_i= 2 \cdot a_{i-1} + 1 \;\;\iff\;\; a_i + 1= 2 \big(a_{i-1} + 1 \big)=2^2\big(a_{i-2}+1\big) = \ldots = 2^i \big(a_0+1\big) = 2^{i+1} $$