Chapter 2 in Concrete Mathematics talks about solving recurrences of the form $$a_{n}T_{n}=b_{n}T_{n-1}+c_{n}$$ by reducing them into a sum.
The authors multiply both sides by a summation factor $s_n$, which satisfies $$s_{n}b_{n}=s_{n-1}a_{n-1}$$, thus the value of $s_n$ can be written as the fraction $$\frac { a_{ n-1 }a_{ n-2 }…a_{ 1 } }{ b_{ n }b_{ n-1 }… b_2}$$
Taking the recurrence: $$T_0 = 0$$$$T_n=2T_{n-1}+1$$ I can see that $b_n=2$ and $a_n=1$, however I don't understand what values to use for values of $a$ and $b$ for remaining $n$.
For finding the value of $s_n$, what will be the values $b_{n-1}, b_{n-2}…b_2$ and $a_{n-1}, a_{n-2}…a_1$?
(The value of $s_n$ for this recurrence is $2^{-n}$)
Best Answer
Your formula gives you $s_n=1/2^{n-1}$, but any constant multiple works equally well, so the fact that the "solution" or someone else says $s_n=1/2^n$ does not imply that you are wrong.