# Finding the $n^{th}$ term of a particular recursive sequence.

Just recently, I encountered this problem.

Prove or disprove that the $$n^{th}$$ term of the sequence $$a_0=0$$ $$a_1=1$$ $$\vdots$$ $$a_k=2\bigg(a_{k-1}+2^{k-1}-2^{k-2}-\bigg\lfloor \frac{2^{k-2}-1}{3}\bigg\rfloor\bigg)-1$$ is given by $$a_n=\frac{(3n+1)\cdot2^n-(-1)^n}{9}.$$

In an attempt to disprove the problem, I tried to solve for the value of $$a_k$$ for $$k=0,1,\ldots,9$$. However, the result of the computations tend to show that the formula for the $$n^{th}$$ term of the sequence above seems to be correct. So my task now is to prove that the formula for the $$n^{th}$$ term of the sequence is correct. However, I do not know how to begin.

Any suggestion/answer on how to solve the problem? In general, are there any available method on how to find the $$n^{th}$$ term of a recursive sequence such as the one above?

• Since a formula for $a_n$ is already suggested in the exercise you can prove it by induction on $n$. – Kavi Rama Murthy Jun 15 '20 at 5:55
• Thank you so much @KaviRamaMurthy for your suggestion. I will now try to do that. But in general, how does one might arrive to the formula for the $n^{th}$ term of the sequence, if we will just start by the sequence themselves? – LeafRadian25 Jun 15 '20 at 6:05
• There are many examples where a formula for $a_n$ in terms of elementary functions of $n$ is impossible. There is no general procedure even when a formula exists. The strategy one uses in general is write down a few terms and try to guess what the formula is. If you make a guess you are still obliged to prove that the formula is correct. – Kavi Rama Murthy Jun 15 '20 at 6:09
• I see. Thank you so much again @KaviRamaMurthy – LeafRadian25 Jun 15 '20 at 6:13
• @KaviRamaMurthy oeis.org is a great resource for seeing if a given sequence is known in the literature. – Math1000 Jun 15 '20 at 6:28

$$a_k=2a_{k-1}+2(2^{k-1}-2^{k-2})-2\lfloor\frac{2^{k-2}-1}{3}\rfloor-1=2a_{k-1}+2^{k-1}-1-2\lfloor\frac{2^{k-2}-1}{3}\rfloor$$.

We want to prove that $$a_n=\frac{(3n+1)2^n-(-1)^n}{9}$$ so assume that this is true for any $$n (this is the induction hypothesis). Now we will prove it is also true for $$k$$ which finishes our proof.

$$a_k=\frac{(3k+1)2^k-(-1)^k}{9}$$ $$\Leftrightarrow$$ $$\frac{(3k+1)2^k-(-1)^k}{9}=2a_{k-1}+2^{k-1}-1-2\lfloor\frac{2^{k-2}-1}{3}\rfloor=\frac{2((3(k-1)+1)2^{k-1}-(-1)^{k-1})}{9}+2^{k-1}-1-2\lfloor\frac{2^{k-2}-1}{3}\rfloor$$ (we replaced $$a_{k-1}$$ using our induction hypothesis)

So we have $$3k\times2^k+2^k-(-1)^k=2(3k\times2^{k-1}-2^k)-2(-1)^{k-1}+9\times2^{k-1}-9-18\lfloor\frac{2^{k-2}-1}{3}\rfloor$$ Simplfying, we get

$$2^k-(-1)^k=2^{k-1}+2^{k+2}-2^{k+1}-2(-1)^{k-1}-9-18\lfloor\frac{2^{k-2}-1}{3}\rfloor$$ $$\Leftrightarrow$$ $$9+18\lfloor\frac{2^{k-2}-1}{3}\rfloor=2^{k-1}+2^k+(-1)^k-(-1)^{k-1}$$

If $$k$$ is even then $$18\lfloor\frac{2^{k-2}-1}{3}\rfloor=6(2^{k-2}-1)$$ so we have $$9+6(2^{k-2}-1)=2^{k-1}+2^k+(-1)^k-2(-1)^{k-1}$$ $$\Leftrightarrow$$ $$3=3$$

If $$k$$ is odd, $$18\lfloor\frac{2^{k-2}-1}{3}\rfloor=6(2^{k-2}-2)$$ so from the same analysis we get the result.

So we win! $$a_n=\frac{(3n+1)2^n-(-1)^n}{9}$$

• Thanks @Vlad for providing a detailed answer. We both arrived at the same solution using induction as suggested by KaviRamaMurthy. As a side question, suppose that only the recursive definition of the sequence is given. I am interested in a method on how to derive the $n^{th}$ term. – LeafRadian25 Jun 15 '20 at 10:13
• also I am so delighted by the word "We Win!". Thank you so much again. – LeafRadian25 Jun 15 '20 at 10:22
• Since this is a linear recurrence, you can simply purely calculate the general term. (This is what i would have done instead of induction if the term wasn;t already given). Then analyzing k mod 2, you get the term (you want to get rid of that floor function and (-1)^n) – user799688 Jun 15 '20 at 10:34
• Thank you again @Vlad for the method. Will try to do that – LeafRadian25 Jun 15 '20 at 10:41