# Easy Induction study problems

### Problem 1

Use strong induction to prove that that the following holds for all natural numbers n and all real numbers $$x \not = 1$$.

$$\displaystyle \sum_{i=0}^n x^i =\frac{x^{n+1}-1}{x-1}$$

Stuck? See the hints.

When you have a proof that seems close to correct, look at the solution.

### Problem 2

Suppose that we draw n lines in the plane, in general position (no lines are parallel, no point belongs to more than two lines). The lines divide up the plane into a set of regions. Prove the following claim, for any positive integer n:

Claim: we can color these regions with two colors, such that adjacent regions (i.e. touching along an edge) never have the same color.

Stuck? See the hints.

When you have a proof that seems close to correct, look at the solution.