# An elementary sequence problem

The sequence {$$a_n$$} is defined by $$a_0=1$$ and $$a_{n+1}=2a_n+1$$ for $$n=0, 1, 2,...$$ What is the value of $$a_4$$?

The answer is 31. I got the right answer, but I'm not sure if I got it "correctly", I feel like there's either something wrong with my notation or my math. My solution goes as follows: \begin{align*} a_{n+1}&=2a_n+1 \hspace{1cm} n\in \mathbb{Z}\ge0 \\ &\implies \sum_{a_n=1}^{a_4}2a_n+1 \\ \text{recall} \ a_0&=1, \text{then}\\ a_1&=3 \\ a_2&=2(3)=6 \\ a_3&=3(3)=9 \\ a_4&=4(3)=12 \\ \therefore \left\{2a_n+1\right\}_{a_1=1}^{a_4}&=31 \end{align*}

The solution given to me, however, states:

Given $$a_0=1$$ and $$a_{n+1}=2a_0+1$$, it is possible to compute successive values for the sequence:

\begin{align*} &a_1=2a_0+1=3 \\ &a_2=2a_1+1=7 \\ &a_3=2a_2+1=15 \\ &a_4=2a_3+1=31 \end{align*}

I noticed my values and their values for $$a_2$$, $$a_3$$ and $$a_4$$ do not match. This feels so on the nose, but what did I do that made me get some wrong solutions for $$a_{n+1}$$ while getting the right answer for the problem itself?

CONTEXT

So, my idea was to take $$2a_n+1$$ from $$a_n$$ to $$a_4$$. I thought this is what adds $$a_{n+1}$$ 4 times (because if $$a_n=a_0$$ then $$n=0$$). I think I made the faulty assumption that the sum from $$n=1$$ to $$n=3$$ I would get the result from $$n=4$$, I don't know - I'm sleep deprived. My first step was to note I would eventually add 1 because starting at $$a_0$$ we get $$1$$ as stated in the problem. Then, I said $$a_{0+1}=2(1)+1=3$$ because, again, $$a_n=(1)$$. This gets us $$a_1=3$$. Then I said $$a_{0+2}=2[2(1)+3]$$ because, at the time, I thought multiplying the original expression by 2 would get us $$a_2$$, in this case being equal to 6; the original expression by 3 to get $$a_3$$, and so on. I basically did this because I didn't know how to approach, say, $$a_{0+2}=2a_n+1$$

• I don't understand your computation at all. What does $a_{n+1}=\sum_{a_n=1}^{a_4} 2a_n+1$ mean? That's a very odd sum. Taken literally, you are claiming that, for all $n$, $a_{n+1}=(2\times 1+1)+(2\times 2+1)+(2\times 3+1)+(2\times 4+1)$. – lulu May 31 at 12:18
• you just did not add 1, $a_2=2\times3 +1=7$ – sirous May 31 at 12:19
• There are five or six conceptual errors in your answer... – Yves Daoust May 31 at 12:39

It was just a flat-out coincidence that you got the same answer.

First of all, note that the sequence that you generated doesn't match the one given. In fact, the sequence you're generating appears to be $$a_n=na_1$$, where $$a_1=3$$. Your calculation of $$a_1$$ from $$a_0$$ is correct, but from there it deviates from the given formula.

What you appear to have tried to do is take the sequence and find a formula for the n$$th$$ term given the equation for any term, which while technically possible, is difficult in general.

If you explain some of your steps more thoroughly and why you did them, perhaps we can help you see why what you did is wrong.

Your notation is incorrect; your big-sigma notation doesn't even make sense, nor do I know what it's meant to communicate, so I'm frankly not sure what to say there.

The notation $$n \in \Bbb Z \ge 0$$ also is incorrect but at least I get what you meant ($$n$$ is a nonnegative integer). You might want to refer to this instead through $$n \in \Bbb N_0$$ ("$$n$$ is a natural number, where we define the naturals to include zero") or by simply making two statements (like saying "$$n \in \Bbb Z, n \ge 0$$"). Or you could even just say explicitly "$$n$$ is a nonnegative integer."

It's important to be aware that while the symbols exist to expediate the communication of the content and serve as a shorthand, you don't have to shorten everything as much as humanly possible and that using your words is often necessary - ease of communication, not brevity, is what is truly important.

You put an overemphasis on these formal symbols when in reality that is hardly necessary here and completely overcomplicates an exercise that would have a one- or two-line solution, and on top of that your inexperience with the notations completely obfuscates what you're doing because you didn't bother to communicate that in words.

I'm not really sure the motivation underlying your solution method - I can't make heads or tails of it, so it's hard to critique beyond saying that it seems just altogether wrong, and that you getting the same answer is probably just coincidence.

As for how to derive the answer, consider working backwards from $$a_4$$ if this helps you. Set $$n=3$$ in the original recurrence; then

$$a_4 = 2a_3 + 1$$

But what's $$a_3$$? We use the recurrence again!

$$a_3 = 2a_2 + 1$$

Similarly,

$$a_2 = 2a_1 + 1$$ $$a_1 = 2a_0 + 1$$

$$a_0$$ is given, so now just plug that into the last formula. That gives you $$a_1$$, which you can use to get $$a_2$$, $$a_3$$, and so on. Of course you don't have to do all this iteration backwards -- most people will simply realize that the recurrence means that we can plug in $$a_0$$ to get $$a_1$$ and that to get $$a_2$$ and so on -- but perhaps this way it's clearer.

• For $n \in \mathbb{Z} \ge 0$ I was trying to say "n=a whole number". In that context, that's correct - but my attempted sum didn't express that because it starts at n=1. Aside from your harshness, working backwards made everything make sense, though. So uh, thanks for that at least. – Lex_i May 31 at 13:31

It seems you might have made a mistake when substituting values into the recursive sequence, and by chance you ended up with $$a_4 = 31$$. Your $$a_2$$ and $$a_3$$ values differ because you're calculating $$a_n = 3n$$ and this is not the expression for $$a_n$$. The working from the solution in the textbook computes each term by the recursive definition. "Take the previous term, multiply it by two and add 1". Perhaps this may be easier to follow?

You cannot calculate $$a_1, a_2, a_3, a_4$$ without using the given relation $$2a_n +1$$. You need to calculate it by the given formula every time you find $$a_n$$.

So, $$a_2=2(a_1)+1$$

or, $$a_2=2.3+1=7$$ and so on.

Moreover, the question asks you to find the term: $$a_4$$, but what you essentially did was the addition of all the numbers from $$a_0$$ to $$a_4$$. The summation you did wasn't required or asked.

Here is perhaps the simplest way of seeing the recursion: Let $$b_n=a_n+1$$ be a new sequence. Note that, $$b_{n+1}=a_{n+1}+1=2(a_n+1)=2b_n$$. Thus, $$b_n=2^{n}b_0$$, where $$b_0=2$$, yielding $$b_n=2^{n+1}$$, and thus, $$a_n=2^{n+1}-1$$. From here you get everything you want about this sequence.

You can see, for instance, that for every odd integer $$k$$, there is a term of this sequence $$a_\ell$$ such that $$k\mid a_\ell$$ (to see this fact, simply note for $$\ell=\varphi(k)-1$$, where $$\varphi(k)$$ is Euler's totient), $$a_\ell\equiv 0\pmod{k}$$ holds). There are many more properties, I leave them to you to explore.

It is not a big deal to show that

$$a_n=2^n+2^{n-1}+2^{n-2}+\cdots1=2^{n+1}-1.$$

Then, the sum that you compute is that of an arithmetic progression (terms $$3n$$, but $$1$$ for the initial one) and

$$s_n=1+3\frac{n(n+1)}2.$$

You had two chances to obtain a match: for $$n=0$$ or $$n=4$$. Well done.