General term of a range

Question

I started to solve a task and I did it. Tasks says:Find the currence formula of the range with these terms:$1,2,4,8 \dots$ I found it: $$X_1=1,X_{n+1}=1+X_1+X_2+\dots+X_n, n\ge1.$$

Now I'm trying to prove with mathematical induction that the general term of the range is $X_n=2^n$.

Can anyone tell me how to prove it?

Thank!

If you look at your formula, you will see that $X_{n+1} = X_n + (X_{n-1} + \ldots + X_1 + 1) = X_n + X_n$. — Daniel Fischer, Jul 03 '13 at 10:53

score 2 · Accepted Answer · answered Jul 03 '13 at 11:52

As Daniel Fischer commented, the recurrence as you wrote it can be simplified to $X_{n+1} = 2X_n$. Your expression for $X_n$ must account for the fact that your started your series from $n = 1$. Hence, it should be $X_n = 2^{n-1}$.

Proof by induction involves two steps. First, prove the base case, which in your question is $n = 1$. Second, prove that the expression holds for $x=n+1$ under the assumption that it holds for $x = n$. This is called the inductive step.

$n = 1 \Rightarrow X_1 = 2^{1-1} = 1$, which proves the base case.
Assume that $X_n = 2^{n-1}$. Now $X_{n+1} = 2X_{n} = 2 \cdot 2^{n - 1} = 2^{n-1+1} = 2^n$, which completes the proof.

Thank you very much! You helped me a lot:) – Student Jul 08 '13 at 17:04 — Student, Jul 08 '13 at 17:04

General term of a range

1 Answers1