1. ## Mathematical Induction

Prove by induction where n is a positive integer:

The greatest number of regions that n straight lines can divide a circle is $\displaystyle \frac {1}{2} (n^2+n+2) , n\geq1$

The problem is, I do not know where/how to start. Can someone give me some hints to begin?

2. Always start by proving that it starts.

Try n = 1 and see.

Try n = 2 and convince yourself. Is it really 4?

Try n = 3 and become a disciple. Is it really 7?

Are we really proving the premise or just the equation?

3. Show for n=1: $\displaystyle \frac{1^{2}+1+2}{2}=2$........true.

Assume $\displaystyle P_{k}$ is true. This the induction hypothesis is

$\displaystyle R(k)=\frac{k^{2}+k+2}{2}$

We must show $\displaystyle P_{k+1}$ is true.

If we add a (k+1)st line, the regions increase by k+1.

$\displaystyle \frac{k^{2}+k+2}{2}+(k+1)=\frac{k^{2}+3k+4}{2}$

$\displaystyle R(k+1)=\frac{(k+1)^{2}+(k+1)+2}{2}=\frac{k^{2}+3k+ 4}{2}$

This shows that $\displaystyle P_{k+1}$ is true and the induction holds. QED.

4. Thanks. So we are proving just proving the equation.