A simple recurrence problem: $L_n=L_{n-1}+n$

Question

I am studying concrete mathematics by Graham Knuth and Patashnik. In the first chapter lines in a plane he focuses on a equeation $$L_n=L_{n-1}+n$$ on expanding $$ \begin{align} L_n&=L_{n-2}+(n-1)+n \\&=L_{n-3}+(n-2)+(n-1)+n \\&=\cdots \\&=\cdots \\&=L_0+1+2+3+\cdots+(n-1)+(n-2) \end{align} $$and so on. Could someone explain how did the number $L_0+1+2+3+\cdots+(n-1)+(n-2)$ come into this series?

Thank you.

Answer 1

It's just working out the equation starting with $L_n$ and ending up with $L_0$:

$$L_n = L_{n-1} + n = L_{n-2} + (n-1) + n = ... = L_2 + 3 + ... + (n-1) + n = L_1 + 2 + 3 + ... + (n-1) + n = L_0 + 1 + 2 + 3 + ... + (n-1) + n$$

Do you see it now?

Answer 2

From $$ {\rm L}_n-{\rm L}_{n-1}=n,\quad n=1,2,3,\cdots, $$ one may just sum the following equalities: $$ \begin{align} {\rm L}_1-{\rm L}_0 &=1 \\{\rm L}_2-{\rm L}_1 &=2 \\{\rm L}_3-{\rm L}_2 &=3 \\{\cdots}\,{\cdots} \\{\rm L}_n-{\rm L}_{n-1} &=n \end{align} $$ to get by a telescoping sum, $$ {\rm L}_n-{\rm L}_{0}=1+2+3+\cdots+n. $$

Answer 3

$$ L_n = L_{n-1} + n $$ so we can write $$ L_{n-1} = L_{(n-1)-1} + (n-1) = L_{n-2} + (n-1) $$ we can put the first two lines together to form $$ L_n = (L_{n-2} + (n-1)) + n $$ we can keep this process going $$ L_{n-2} = L_{n-3} + (n-2) $$ or $$ L_n = L_{n-3} + (n-2) + (n-1) + n = L_{n-3} + \sum_{k=0}^2 (n-k) $$ or $$ L_n = L_{n-10} + \sum_{k=0}^9 (n-k) $$ or $$ L_n = L_{n-m} + \sum_{k=0}^{m-1}(n-k) $$ lets take $m = n$ then we have $$ L_n = \sum_{k=0}^{n-1}(n-k) $$