Induction

1. Evaluating a Series

If we have a finite series there are two ways of evaluating it.  The first way is computation by hand.

Example:

S
n = 15 (2n-1)

is

1 + 3 + 5 + 7 + 9 = 25.

Notice that we just plugged in the values 1,2,3,4, and 5 for n and added up the results.

Example:

S
n=2100 (1/n)

You can try this by hand, but you will become very bored and discouraged as you find out that you need to add up 100 numbers.  Instead we use our calculator:

sum seq(1/x,x,2,100,1) = 4.187

we find the sum and seq features under Math -> Misc.  sum means that we are adding up the terms, seq means that it is a sequence, 1/x is our function, x is our variable, 2 is where we start, 100 is where we stop, and 1 means that we are not skipping numbers.

2. Mathematical Induction

Suppose that we want to find

S
i = 1100(i)

We can pair the first and last terms to get

1 + 100 = 101

then pair the second and penultimate term to get

2 + 99 + 101

again.  We can do this repeatedly until we arrive at the 50th and 51st terms to get 101.  in all we have

101(100)/2

We can conjecture that for any n,

To prove this we use mathematical induction which means the following:

If the theorem is true for the first one and if the theorem is true for the next one given the truth of the preceding one, then the theorem is true for all n.

The steps for using induction are as follows:

1. Plug in n = 1 and verify the theorem.

2. We write:  Assume that the theorem is true for n = k -1.  Plug in k - 1 for n and write down the statement.

3. Write down the statement of the theorem for n = k by plugging in k for n.

4. Do some algebra or logic to write what you have in 3) as a part with the statement from 2 and other stuff.

5. Use the theorem for n = k - 1 to rewrite your expression from part 4.

6. Do more algebra to write the conclusion of the theorem for n = k

7. Write:  "By induction we can conclude that the theorem is true."

For our example,  we follow our steps:

1.   which checks.

2. Assume that the theorem is true for n = k -1.  Then

3. We write S i = 1k ( i)

4.  =  k + (k - 1)(k)/2

5. = 2k/2 (k2 - k)/2 = (k2 + k)/2  = k(k + 1)/2

6. "By induction we can conclude that the theorem is true."

Exercise: Show that

3. Second Principle of Mathematical Induction

To prove a theorem using induction, it is ok to assume that the theorem is true for all

n < k

Exercise

Let u =
 1 1 1 0

and let un be the nth Fibonacci number, prove that
un =
 un+1 un un un-1
for all n > 2

1.  For n = 2, we have
u2 =
 2 1 1 1

which checks

2. Now assume that the theorem is true for n = k - 1, then
uk - 1 =
 un un-1 un-1 un-2

1. We have   uk

2.           =  uuk - 1

3.          =
 1 1 1 0
 un un-1 un-1 un-2
=
 un + un-1 un un-1 + un-2 un-1

4.           =
 un+1 un un un-1

5. "By induction we can conclude that the theorem is true."