# Concrete Mathematics 2.10 - 2.13 Cannot find part of the solution

I've seen a few other questions on this section, but none match my issue, I feel like I'm missing something super obvious. Everything in here seems to make sense, I can follow along everything, except I'm missing part of the answer (at the end of post; most of the middle part might not be needed by the experts). "Background" also should not be needed, as the "Starting Point" is confirmed in the book, but it is generally described just in case.

Background: Equation starts as this: (1st) $C_0 = C_1 = 0$

$$C_n = n+1 + \frac{2}{n}\sum_{k=0}^{n-1}C_k \hspace{3mm}for\hspace{2mm}n > 1$$ After multiplying both sides by $n$(2nd), $n$ is replaced by $n-1$(3rd) and the 3rd equation is subtracted from the 2nd, yielding the equation below which is in a "special form" of $aT_{n} = bT_{n-1} + c$ (if anyone knows the name of this form or 'trick' I'd like to know).

Starting Point: $$C_0 = C_1 = 0, C_2 = 3$$ $$nC_n = (n+1)C_{n-1} + 2n \hspace{3mm}for\hspace{2mm}n > 2$$ So $a=n, b=n+1, c=2n$.

The summation factor ($s_n$) ends up being $\frac{2}{(n+1)n}$

Setting $S_n = s_na_nT_n$ yields $S_n = S_{n-1} + s_nc_n$ And then you put this into a sum: $$S_n = s_1b_1T_0 + \sum_{k=1}^ns_kc_k$$ $$S_n = ( (\frac{2}{2}\times 2 \times 0) + \sum_{k=1}^n\frac{2}{(k+1)k}2k)$$ Isolate sum by undoing summation factor: $$T_n = \frac{1}{s_na_n}(s_1b_1T_0 + \sum_{k=1}^ns_kc_k)$$ $$T_n = \frac{(n+1)n}{2n}( (\frac{2}{2}\times 2 \times 0) + \sum_{k=1}^n\frac{2}{(k+1)k}2k)$$ When I calculate this out, I get $s_1b_1T_0 = 0$ (because $T_0 = 0$, (right?)) and multiplying out the sum yields (My Answer):

$$C_n = 2(n+1)\sum_{k=1}^n\frac{1}{k+1}$$

Which is close to the actual answer, which is

$$C_n = 2(n+1)\sum_{k=1}^n\frac{1}{k+1} - \frac{2}{3}(n+1)\hspace{3mm}for\hspace{2mm}n > 1$$

I cannot figure out where the $-\frac{2}{3}(n+1)$ comes from.

I'm guessing maybe it's from the $s_1b_1T_0$ but cannot seem to get that to work, even if I set 0 to be 2 or something. (Starting with a different index as suggested by another post, but doesn't make too much sense to me to do that)

What am I doing wrong/missing? Been trying to figure this out much too long, and I'm about to go crazy.. Seems like missing multiplicand is $-\frac{4}{3}$ but I can't seem to find it anywhere. I'm trying various ideas to make $s_1b_1T_0 = -\frac{4}{3}$.

$s_1b_1 = 2$ so $T_0$ logically should be $-\frac{2}{3}$, but I don't see how. Interestingly, plugging $n=0$ into the final answer yields $-\frac{2}{3}$ but that info isn't available until it's solved.

• If thats $nCr$ then any value of n,r cant make $nCr=0$ maybe iys something else if so whats it Jan 10, 2016 at 11:34

The problem is that the summation factor $s_n$ isn’t defined for $n=0$ and $n=1$. Thus, you can go back only as far as $S_2$:
\begin{align*} S_n&=S_2+\sum_{k=3}^ns_kc_k\\ &=s_2a_2C_2+\sum_{k=3}^ns_kc_k\\ &=\frac13\cdot2\cdot3+\sum_{k=3}^n\frac{4k}{k(k+1)}\\ &=2+4\sum_{k=3}^n\frac1{k+1}\;, \end{align*}
\begin{align*} C_n&=\frac{S_n}{s_na_n}\\ &=\frac{n+1}2\left(2+4\sum_{k=3}^n\frac1{k+1}\right)\\ &=(n+1)\left(1+2\sum_{k=1}^n\frac1{k+1}-2\sum_{k=1}^2\frac1{k+1}\right)\\ &=(n+1)\left(1+2\sum_{k=1}^n\frac1{k+1}-\frac53\right)\\ &=(n+1)\left(2\sum_{k=1}^n\frac1{k+1}-\frac23\right)\\ &=2(n+1)\sum_{k=1}^n\frac1{k+1}-\frac23(n+1)\;, \end{align*}
for $n\ge 3$. Substituting $n=2$, we see that the formula still works, but it fails for $n=0$ and $n=1$.