Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
Litvin
Posts:
270
Registered:
12/6/04
|
|
Re: [ap-calculus] mathematical induction
Posted:
Nov 4, 2009 12:10 PM
|
|
At 11:17 PM 11/3/2009, Huffhaus63 wrote:
>I agree that proving the sum of the first n odd integers is n^2
>seems artificial, as well as doing the other examples usually used
>in introducing the concept.
I don't think it is necessarily artificial, if put in the right
context. In general, math induction is useful for proving properties
of recurrence relations; in computer science it is used to prove
correctness and study properties of recursive algorithms. Surely,
a(1) = 1, a(n) = a(n-1) + 2 or s(1) = 1, s(n) = s(n-1) + (2n-1) are
very simple examples of recurrence relations. Still, they might be
useful before moving on to more interesting examples. Such as: show
that f(1) + f(2) + ... + f(n) = f(n+2) - 1, where f(n) is the n-th
Fibonacci number. This proof would be quite cumbersome if you used
the closed-form formula for f(n), which is cumbersome itself. With
math induction the proof is very easy.
Another example: show that the n-th Fibonacci number f(n) >= (3/2)^n.
A simple recursive algorithm example is the Towers of Hanoi puzzle
http://en.wikipedia.org/wiki/Tower_of_Hanoi. How can we find the
smallest number of moves needed to solve the puzzle with n disks?
From the recurrence relation f(1) = 1, f(n) = 2*f(n-1) + 1, where
f(n) is the number of moves. Using math induction it is easy to show
that f(n) = 2^n - 1.
Gary Litvin
www.skylit.com
====
Course related websites:
http://apcentral.collegeboard.com/calculusab
http://apcentral.collegeboard.com/calculusbc
---
To unsubscribe click here:
http://lyris.collegeboard.com/read/my_forums/?forum=ap-calculus
To change your subscription address or other settings click here:
http://lyris.collegeboard.com/read/my_account/edit
|
|
|
|
