# 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.