In the sequence $1,3,7,15,31\ldots$ each term is $2\cdot\text{immediately preceding term}+1$. What is the $n$-th term?
I readily see that it is $2^n-1$, but how can I deduce the $n$-th term from the given pattern i.e. $n$-th term $= 2\cdot(n-1)\text{th term} + 1$ without computation.
$\endgroup$ 26 Answers
$\begingroup$Hint: Compare to the sequence of powers of $2$.
$\endgroup$ $\begingroup$$$a_1=1 \hspace{1cm} a_{n+1}=2a_n+1$$
You can write the second equality as: $$a_{n+1}+1=2(a_n+1)$$
Therefore:$$a_n+1=(a_1+1)\cdot2^{n-1}=2^n$$
And finally: $$a_n=2^n-1$$
$\endgroup$ 3 $\begingroup$Here is how I deduced the formula from your title before I saw the formula in your post.
Your recursive relation multiplies the previous term by two. What other sequence do I know that does that? Ah, yes, $2^n$ also does that. I will compare the given sequence with my sequence. Oh, they differ by one. OK, the formula must be
$$a_n=2^n-1$$
If that had not worked, I would next have tried the method of finite differences. Take the difference between successive terms, and perhaps look at the differences of those differences. That often leads to a formula for the sequence. (This is what @Claude Leibovici suggested in his comment.)
$\endgroup$ $\begingroup$The recursion relation is $a_{n+1}=2a_n+1$, with $a_1=1$. Consider $b_n=a_n+1$; then $$ b_{n+1}=a_{n+1}+1=2a_n+1+1=2(a_n+1)=2b_n $$ and $b_1=2$. Then $b_n=2^n$ by the recursive definition of powers and so $a_n=b_n-1=2^n-1$.
$\endgroup$ 2 $\begingroup$Here is an explicit proof by induction. Given that $a_{n+1}=2a_n+1$ for $n=0,1,...$, with $a_0=1$ prove the proposition $\mathcal P(n):\;\,a_n=2^n-1$ for $n=0,1,...$ .
We are given that $\mathcal P(n)$ holds for $n=0$. Suppose now that we know $\mathcal P(n)$ for $n=k$; that is, $\mathcal P(k):\;\,a_k=2^k-1$. Now $a_{k+1}=2a_k+1=2(2^k-1)+1=2^{k+1}-1$. We have shown that $\mathcal P(k)\Rightarrow\mathcal P(k+1)$. Hence, by induction, $\mathcal P(n)$ holds for all $n=0,1,...$ .
$\endgroup$ 2 $\begingroup$I know this is an old post, but I ended up having to solve the same question the other day, and initially looked here first.
Firstly we see the recursive formula $x_{n+1} = 2x_{n} + 1$. Letting our first term be $x_1$, then $$x_2 = 2x_1 + 1,$$ $$x_3 = 2x_2 + 1,$$ $$x_4 = 2x_3 + 1.$$ Rewriting these in terms of $x_1$ and looking at the powers of two yields: $$x_2 = 2x_1 + 1 = 2^1x_1 + 1$$ $$x_3 = 4x_1 + 3 = 2^2x_1 + 3$$ $$x_4 = 8x_1 + 7 = 2^3x_1 + 7$$ It can be seen that $x_n = 2^{n-1}x_1 + x_{n-1}$. We already know that $x_{n} = 2x_{n-1} + 1$. This can rearranged to show $x_{n-1} = \frac{x_{n}-1}{2}$ therefore: $$x_n = 2^{n-1}x_1 + x_{n-1}$$ $$x_n = 2^{n-1}x_1 + \frac{x_n-1}{2}$$ $$2x_n = 2*2^{n-1}x_1 + x_n-1$$ $$x_n = 2^nx_1-1$$ And in our case $x_1 = 1$ therefore $$x_n = 2^n-1$$
$\endgroup$
