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?


1 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\,$.

  • $\begingroup$ thanks,in the repertoire method is there a way to know which function should is use or is it just an intelligent guess $\endgroup$
    – Karan
    Jan 11, 2022 at 6:04
  • $\begingroup$ @Karan That's an educated guess for the most part. See also the accepted answer to Mathematical explanation for the Repertoire Method. $\endgroup$
    – dxiv
    Jan 11, 2022 at 6:08
  • $\begingroup$ this isn't relevant but do you think concrete mathematics by Donald knuth is possible to be done by a high schooler $\endgroup$
    – Karan
    Jan 11, 2022 at 7:03
  • $\begingroup$ @Karan That depends a lot on both the high school (curriculum) and the student (enthusiasm). I'd say it is possible, though with some caveats. Don't expect it to be all smooth and easy. Be prepared to go back and re-read parts of it over and again to find what you missed on previous reads. If some things don't make sense even after re-reads, it is quite possible that they presume certain math that you have not covered, yet. All in all, it certainly can't hurt to give it a try - just don't set the expectations too high, and don't get too upset if not everything works out the first time around. $\endgroup$
    – dxiv
    Jan 11, 2022 at 7:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .