| (8 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| + | =[[MA375]]: The Principle of Induction= | ||
| + | Lecture Notes | ||
| + | ---- | ||
Example: | Example: | ||
| − | Prove that <math> \forall n\in{\mathbb N}, n^5-n | + | Prove that <math> \forall n\in{\mathbb N}, n^5-n </math> is a multiple of n. |
| + | |||
| + | Base case: n=0... <math> 0^5=0 </math> as we want | ||
| + | |||
| + | Inductive step: Assume that 5 divides <math> n^5-n </math> and show that 5 divides <math> (n+1)^5-(n+1) </math> | ||
| + | |||
| + | P(1) = 1-1 = 0 (true,divisible by 5) | ||
| + | |||
| + | P(2) = 32-2 = 30 (true,divisible by 5) | ||
| + | |||
| + | let P(m) be true, P(m+1) = <math> (m+1)^5-m </math> | ||
| + | |||
| + | P(m+1) = <math> (m^5+1)+5*(other terms) </math>. | ||
| + | |||
| + | which is divisible by 5 since P(m) is true. | ||
| + | |||
| + | Hence 5| <math> n^5-n </math> | ||
| + | ---- | ||
| + | [[Main_Page_MA375Fall2008walther|Back to MS375, Fall 2008, Prof. Walther]] | ||
Latest revision as of 08:08, 20 May 2013
MA375: The Principle of Induction
Lecture Notes
Example: Prove that $ \forall n\in{\mathbb N}, n^5-n $ is a multiple of n.
Base case: n=0... $ 0^5=0 $ as we want
Inductive step: Assume that 5 divides $ n^5-n $ and show that 5 divides $ (n+1)^5-(n+1) $
P(1) = 1-1 = 0 (true,divisible by 5)
P(2) = 32-2 = 30 (true,divisible by 5)
let P(m) be true, P(m+1) = $ (m+1)^5-m $
P(m+1) = $ (m^5+1)+5*(other terms) $.
which is divisible by 5 since P(m) is true.
Hence 5| $ n^5-n $
