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?
$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}$