Discrete Mathematics: Elementary and Beyond

2 Combinatorial Tools

2.1 Induction

It is time to learn one of the most important tools in discrete mathematics.
We start with a question:

We add up the firstnodd numbers. What do we get?

Perhaps the best way to try to find the answer is to experiment. If we
try small values ofn, this is what we find:

1=1

1+3=4

1+3+5=9

1+3+5+7=16

1+3+5+7+9=25

1+3+5+7+9+11=36

1+3+5+7+9+11+13=49

1+3+5+7+9+11+13+15=64

1+3+5+7+9+11+13+15+17=81

1+3+5+7+9+11+13+15+17+19=100

It is easy to observe that we get squares; in fact, it seems from these
examples thatthe sum of the firstnodd numbers isn^2. We have observed