2

From Concrete Mathematics, there is a problem called Lines in the Plane on Page 7... At one point the recurrence is described like so:

$L_n = L_{n-1} + n$

I'm not clear on how this gets accomplished during the conversion to closed form:

$L_{n-1} + n = (\frac{1}{2}(n-1)n+1) = \frac{1}{2}n(n+1)+1$

This is described as "the key induction step"...

I've looked back through my algebra notes regarding FOIL, polynomials, etc. but I'm not finding the term/method for working this out.

Any ideas?

Kevin Long
  • 5,159
JacobIRR
  • 147

1 Answers1

2

At that point the authors have explained why $L_n$ satisfies the recurrence

$$L_n=L_{n-1}+n$$

for $n>0$, with $L_0=1$, and are proving by induction on $n$ that this implies that

$$L_n=\frac12n(n+1)+1\tag{1}$$

for each $n\ge 0$. The base case of the induction, which they don’t bother to mention, is the $n=0$ case, and indeed

$$\frac12\cdot0\cdot(0+1)+1=1=L_0\;.$$

Now they carry out the induction step: they assume that $(1)$ holds for $n-1$ and use the recurrence to show that in that case it necessarily holds for $n$ as well. For $n-1$ the closed form $(1)$ gives

$$L_{n-1}=\frac12(n-1)\big((n-1)+1\big)+1=\frac12(n-1)n+1=\frac12n(n-1)+1\;,$$

so the recurrence tells us that

$$\begin{align*} L_n&=L_{n-1}+n\\ &=\frac12n(n-1)+1+n\\ &=\frac{n^2}2\color{crimson}{-\frac{n}2}+1+\color{crimson}n\\ &=\frac{n^2}2\color{crimson}{+\frac{n}2}+1\\ &=\frac12(n^2+n)+1\\ &=\frac12n(n+1)+1\;. \end{align*}$$

We can now conclude by induction that $(1)$ holds for all $n\ge 0$.

Brian M. Scott
  • 616,228
  • I can see that this works out, but what is it actually called when you go from :Ln=Ln−1+n ......to: 1/2n(n−1)+1+n – JacobIRR Sep 29 '16 at 19:15
  • @Jacob: That’s simply substituting the value of $L_{n-1}$ given by the closed form into the recurrence for $L_n$. – Brian M. Scott Sep 29 '16 at 19:27
  • I'd like to check my understanding of the logical leap implied by the red coloured parts in the step-by-step explanation. It looks like we're going from the "closed form - 1" to just "closed form" hence changing $-\frac {n}{2}$ to $+\frac {n}{2}$ and removing $n$. I.e. this was not an algebraic manipulation but rather a logical explanation.Thus by adapting our proposed solution like this we prove it works for all cases? – Friedrich 'Fred' Clausen Nov 16 '19 at 02:18