Solve through iteration $T(n)=T(n-1)+n$

Question

My problem with this is the final step. Through iterative substitution, I come up with the following: $$T(n) = T(n-4) + (n-3) + (n-2) + (n-1) + n$$

which leads to the general form: $$T(n) = T(n-k) + kn - \frac{[k(k-1)]}{2}$$

The restrictions are $T(1)=1$ and $n=2^k-1$. What I am doing at this point is solving for $k$, when $T(1) = 1$ which gives me : $$n = 2^k - 1$$ $$n + 1 = 2^k$$ $$2 = 2^k$$ ($n=1$, since this is for $T(1)=1$)

$$1 = k$$

plugging back in I just come up with the original formula which is obviously not correct.

What am I doing wrong in the final step (if that really is my problem)? Based on other examples I have seen, this would work out nicely if I can put $k$ in terms of $n$ instead of a constant, but I am drawing a blank on how to do this and I cannot find it anywhere.

Answer 1

Alternatively, one may use a telescoping sum. From $$ T(k)-T(k-1)=k, \qquad k=1,2,3,\cdots, \tag1 $$ one gets $$ \sum_{k=1}^n \left(T(k)-T(k-1)\right)=T(n)-T(0)=\sum_{k=1}^n k, \qquad n\ge1, $$ giving

$$ T(n)=\frac{n(n+1)}2+T(0),\qquad n\ge1. $$

Answer 2

$$\begin{align}T(n)&=T(n-1)+n\\T(n)&=T(n-2)+(n-1)+n\\T(n)&=T(n-3)+(n-2)+(n-1)+n\\ &\vdots\\T(n)&=T(n-k)+(n-k+1)+(n-k+2)+\cdots+n\\ &\vdots\\T(n)&=T(1)+2+3+\cdots+n\\T(n)&=1+2+3+\cdots+n\\T(n)&=\frac{n(n+1)}{2}\end{align}$$

Answer 3

$\begin{array}{rcl}T(n) &=& T(n-1) + n \\ &=& T(n-2) + (n-1) + n \\ &=& \ldots \\ &=& T(n-[n-1]) + (n-[n-2]) + (n-[n-3]) + \ldots + n \\ &=& T(1) + 2 + 3 + \ldots + n \\ &=& 1 + 2 + 3 + \ldots \\ &=& \sum_{j=1}^{n}j \\ &=& \frac{1}{2}n(n+1) \end{array}$

If $n = 2^{k}-1$ then $T(n) = T(2^{k}-1) = \frac{1}{2}(2^{k}-1)(2^{k}-1+1) = (2^{k}-1)2^{k-1}$