0
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ Since a formula for $a_n$ is already suggested in the exercise you can prove it by induction on $n$. $\endgroup$ – Kavi Rama Murthy Jun 15 '20 at 5:55
  • $\begingroup$ 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? $\endgroup$ – LeafRadian25 Jun 15 '20 at 6:05
  • 2
    $\begingroup$ 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. $\endgroup$ – Kavi Rama Murthy Jun 15 '20 at 6:09
  • $\begingroup$ I see. Thank you so much again @KaviRamaMurthy $\endgroup$ – LeafRadian25 Jun 15 '20 at 6:13
  • $\begingroup$ @KaviRamaMurthy oeis.org is a great resource for seeing if a given sequence is known in the literature. $\endgroup$ – Math1000 Jun 15 '20 at 6:28
0
$\begingroup$

$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<k$ (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}$

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – LeafRadian25 Jun 15 '20 at 10:13
  • $\begingroup$ also I am so delighted by the word "We Win!". Thank you so much again. $\endgroup$ – LeafRadian25 Jun 15 '20 at 10:22
  • $\begingroup$ 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) $\endgroup$ – user799688 Jun 15 '20 at 10:34
  • $\begingroup$ Thank you again @Vlad for the method. Will try to do that $\endgroup$ – LeafRadian25 Jun 15 '20 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.