1

$$T(n) =\begin{cases}5, & \text{if $n=1$} \\2T(n-1)+3n+1, & \text{if $n\geq 2$}\end{cases}$$

Now the answer is as such:

  1. $T(n)=5\cdot 2^{n-1}+\sum_{i=2}^n2^{n-i}(3i+1)$, which I certainly understand.
  2. $=(3n+6)2^{n-1}-3n-1-3\sum_{i=1}^{n-2}i\cdot 2^i=15\cdot 2^{n-1}-3n-7$, which throws me a big curve ball right immediately without any sense.

Could anyone explain to me the drastic transition algebraically?

Andes Lam
  • 354

1 Answers1

0

A change of variable $j=n-i$ gives: \begin{align} T(n) &=5\cdot 2^{n-1}+\sum_{i=2}^n2^{n-i}(3i+1)\\ &=5\cdot 2^{n-1}+\sum_{j=0}^{n-2}2^j(3(n-j)+1)\\ &=5\cdot 2^{n-1}+(3n+1)\sum_{j=0}^{n-2}2^j-3\sum_{j=0}^{n-2}j2^j\\ &=5\cdot 2^{n-1}+(3n+1)(2^{n-1}-1)-3\sum_{j=0}^{n-2}j2^j\\ \end{align} Now you need: \begin{align} \sum_{i=0}^{n-1}ix^{i-1} &=\frac d{dx}\sum_{i=0}^{n-1}x^i\\ &=\frac d{dx}\frac{x^n-1}{x-1}\\ &=\frac{nx^{n-1}(x-1)-(x^n-1)}{(x-1)^2}\\ &=\frac{(n-1)x^n-nx^{n-1}+1}{(x-1)^2} \end{align} which for $x=2$ become: $$\sum_{i=0}^{n-1}i2^{i-1}=(n-1)2^n-n2^{n-1}+1$$

Fabio Lucchini
  • 16,054
  • Needless to say, this is so elegant. One more question, is this some kind of classical discovery such as the Fermat's little theorem or a result of different lemmas? I feel curious about this because I seem to have zero impression after studying series and sequence 2 years ago. – Andes Lam Feb 17 '20 at 13:03
  • 1
    @AndesLam: I think this is only an application of differential calculus. – Fabio Lucchini Feb 17 '20 at 13:13