confusion in solving a recursion by repertoire method

Question

i am a high schooler and was trying to read concrete mathematic by donald knuth.The first chapter talked about repertoire method and i had never heard of it.after some videos i got the idea and was able to solve simple recursions.then i reached this question $$T_{n}=2+2*T_{n-1}$$ $$T_0=0$$ so i have solved recursions like $T_n=T_{n-1}+n-2$ but never those with $2*T_{n-1}$ now this recursion can also be find by unwinding and gives the answer $2^{n+1}-2$ but i want to solve it by repertoire.so i did this. $$A_{n}=2^n+1;$$ $$A_n=2*A_{n-1}+a$$ by solving $$a=-1$$ so, $$A_n=A_{n-1}-1$$ now $$T_n=\alpha*A_n$$ by solving i get $\alpha=-2$ so T_n becomes $$T_n=-2^{n+1}-2$$ which is wrong.however if i choose $A_n=2^n-1$.i get the answer why cant i get the answer by the method above,and how can i know which function to use for future?

Answer 1

i want to solve it by repertoire.so i did this: $\;\;\;A_{n}=2^n+1$

[...] now: $\;\;\;T_n=\alpha \cdot A_n$

You are basically assuming that $\,T_n\,$ has the form $\,T_n = \alpha \cdot 2^n+\alpha\,$, but that's not the case. It is easy to verify that your end result $\,T_n = -2^{n+1}-2\,$ does not satisfy the original recurrence $\,T_{n}=2 \cdot T_{n-1}+2\,$, and that's because of the (wrong) assumption you made in the beginning.

You could solve it this way by starting with a slightly more general $\,A_n = \alpha \cdot \,2^n + \beta\,$. Then, eliminating $\,2^n\,$ between two consecutive relations, you get $\,A_n=2 \cdot A_{n-1}-\beta\,$. This matches the original recurrence $\,T_{n}=2 \cdot T_{n-1}+2\,$ iff $\,\beta=-2\,$, then $\,A_0=0\,$ implies $\,\alpha=1\,$, so in the end the solution is $\,T_n = 2^n-2\,$.

The more direct way to solve it is add $\,2\,$ on both sides and rewrite it as $\,T_n+2 = 2 \cdot \left(T_{n-1}+2\right)\,$, which indicates that $\,T_n+2\,$ is a geometric progression with common ratio $\,2\,$.