1

I think I'm not seeing the woods for the trees. In the recurrence relation below, how does this part

We know that T(0) = 1,
so, we assume n - k = 0
Thus, k = n

work please? I.e. why can we assume n - k = 0?

The recurrence relation for T(n) is given as

T(n) = T(n-1) + 1, if n > 0;
     = 1 , if n = 0

T(n) = T(n-1) + 1 -----------------(1)
T(n-1) = T(n-2) + 1 -----------------(2)
T(n-2) = T(n-3) + 1 -----------------(3)
Substituting (2) in (1), we get
T(n) = T(n-2) + 2 ------------------(4)
Substituting (3) in (4), we get
T(n) = T(n-3) + 3 ------------------(5)
If we continue this for k times, then
T(n) = T(n-k) + k -----------------(6)

We know that T(0) = 1,
so, we assume n - k = 0
Thus, k = n


By substituting the value of k in (6) we get
T(n) = T(n-n) + n
T(n) = T(0) + n
T(n) = 1 + n
```
Robin Andrews
  • 957
  • They have argued that $T(n)=T(n-k)+k$ for any $n$ and any $k≤n$. Taking the special case $k=n$ yields $T(n)=T(0)+n=1+n$. – lulu Oct 05 '21 at 14:34
  • They want to use $T(n)=T(\color{blue}{n-k})+\color{brown}k$ to find a simplified expression for $T(n)$. Since it is known that $T(\color{blue}0)=1$, when $\color{blue}{n-k}=\color{blue}0$ it works to say $T(n)=T(\color{blue}0)+\color{brown}k=T(0)+\color{brown}n$ (since $\color{brown}k=\color{brown}n$ when $n-k=0$) – J. W. Tanner Oct 05 '21 at 14:36

2 Answers2

1
T(n) = T(n-k) + k -----------------(6)

We know that T(0) = 1,
so, we assume n - k = 0
Thus, k = n

I think I'm not seeing the woods for the trees. why can we assume n - k = 0?

You're not missing the forest for the trees; it doesn't make sense for the author to use the word “assume” (to suppose without proof), which suggests that the step is tentative (it's not).

All the author is doing is setting (“putting”) $k=n$; this is valid, since equation $(6)$ applies for each $n\in\mathbb N$ and each $k\in\mathbb N.$ In so doing, the equation becomes: $$T(n)=T(0)+n$$$$=1+n.\tag7$$

Comparing $(1)$ and $(7)$ gives $$T(n-1)=n,$$ so $$T(n)=n+1.$$

ryang
  • 38,879
  • 14
  • 81
  • 179
0

Hint.

We have

$$ \cases{ T_n-T_{n-1}=1\\ T_{n-1}-T_{n-2} = 1\\ \vdots\\ T_1-T_0 = 1 } $$

After adding all rows we have

$$ T_n = n + T_0 $$

Cesareo
  • 33,252