0

Solving $T(n)=T(n-1)+c\cdot \log n,\quad T(1)=d$

Attempt:

I tried iteration method:

$$T(n)=\color{blue}{T(n-1)}+c\cdot \log n,\quad T(1)=d$$

$$\color{blue}{T(n-1)}=\color{red}{T(n-2)+c\cdot \log (n-1)}$$

$$T(n)=\color{red}{T(n-2)+c\cdot \log (n-1)}+c\cdot \log n$$

$$...\implies T(n)=T(n-k)+c\cdot \sum_{k=1}^{n} \log (1-k+n)$$

How to solve? pleaaassse!!

Error 404
  • 1,892
  • 1
  • 11
  • 23
  • Your recursive formula is slightly wrong, see the answers below (you should not sum over $k$, but over another index and only until $k$) – 57Jimmy Jan 20 '18 at 15:45

2 Answers2

3

You do have to remark that for any induction relation filling the form $$ T_{n+1}=T_n+f(k) \text{ with }T_1=b $$ Then $$ \sum_{k=1}^{n}\left(T_{n+1}-T_n\right)=\sum_{k=1}^{n}f\left(k\right) $$ The first sum is a telescopic one it only has the last and first one left $$ T_{n+1}-T_1=\sum_{k=1}^{n}f\left(k\right) $$ Hence for all $n \in \mathbb{N}^{*}$ $$ T_{n}=\sum_{k=1}^{n-1}f\left(k\right)+T_1 $$ Apply it for $T_1=d$ and $f(x)=c\ln\left(x\right)$ Then

$$ T_{n}=d+c\sum_{k=1}^{n}\ln\left(k\right)=\ln\left(\prod_{k=1}^{n}k\right)=d+c\ln\left(n!\right) $$

Atmos
  • 7,369
1

It should be

$$ T(n) = T(n-k) + c\cdot \sum_{i=0}^{k-1} \log(n-i).$$

This holds for all $n-1 \ge k \ge 1$. In particular, for $k=n-1$,

$$ T(n) = d + c\cdot \sum_{i=0}^{n-2} \log(n-i) = d + c \cdot \log(n!).$$

57Jimmy
  • 6,266