3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Can someone add the right tags to the question? My reputation is too low to add "recurrence". $\endgroup$
    – Vibhav
    Dec 29, 2013 at 8:03
  • $\begingroup$ You mean you want $s_n b_n = s_{n-1}a_{n-1}$. All the $b$'s are equal and so are all the $a$'s. So $s_n$ would be $(1/2)^{n-1}$. $\endgroup$
    – user44197
    Dec 29, 2013 at 8:06
  • $\begingroup$ The problem is that the value of $s_n$ is $(1/2)^{n}$ instead of $(1/2)^{n-1}$ (which I thought to be the answer). $\endgroup$
    – Vibhav
    Dec 29, 2013 at 8:08
  • $\begingroup$ Depends on where you start the indexing. Trick is to get rid of $a$'s and $b$'s. Whether you use $n$ or $n-1$ depends on what you are given: $T_0$ or $T_{-1}$. Just have to work it out. $\endgroup$
    – user44197
    Dec 29, 2013 at 8:12
  • 2
    $\begingroup$ Then you are free to pick $a_0$ and $s_0$. If you pick $s_0=1$ then $s_n$ is $(1/2)^n$. If you pick it as something different, then $s_n = s_0 (1/2)^n$. So $s_n$ is not unique and can be scaled as you want. If you pick $s_0 = 2$ then $s_n=(1/2)^{n-1}$. There is no correct answer. It is a matter of taste as to where you start. $\endgroup$
    – user44197
    Dec 29, 2013 at 8:25

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ how can I get the value of s0? Can I use formula for sn to calculate s0? (sorry but I don't know how to put subscripts) $\endgroup$
    – Sнаđошƒаӽ
    Mar 26, 2015 at 12:31

You must log in to answer this question.

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