MandysNotes

Friday, 07 March 2014 21:08

Mathematical Induction

By  Gideon
Rate this item
(0 votes)

For a function \(f(n)\) of a natural number \(n,\) we can prove that \(f(n)\) has the property P, for all \(n\), if we can do two things:

  •  prove that P is true for \(f(n)\) when \(n\) = 1;
  • second: prove that if P is true for \(f(n)\), then P is also true for \(f(n+1)\).


This process is called mathematical induction. 



Induction can also be used to define functions of a natural number \(n\).

For example, we can define a function \(s(n)\) by:

  •  \(s(1) = 1\);
  •  \(s(n+1) = (n+1) + s(n).\) 


Then:

  • \( s(2) = 2 + s(1) = 2 + 1= 3\);
  •  \(s(3) = 3 + 2 + 1;\) 
  •  etc. 



Evidently, another way to express this function is:

 

\[ s(n) = \sum_{i=i}^{n}{i}. \]

Claim:

\[ s(n) = \sum_{i=i}^{n}{i} = \frac{(n+1)(n)}{2} \]


We will prove this  claim  by induction.

Proof:


For \(n = 1\):
\[ s(n) = s(1) = 1 ,\]

\[ = \frac{(1+1)(1)}{2} = \frac{(n+1)(n)}{2}. \]
If

\[ s(n) = \frac{(n+1)(n)}{2}, \]
then
\[ s(n+1) = (n+1) + \frac{(n+1)(n)}{2}.\]

But,
\[ (n+1) + \frac{(n+1)(n)}{2} = \frac{2(n+1) + (n+1)(n)}{2} \]


\[ \frac{(2n + 2) + n^{2} + n}{2}\]

 

\[ = \frac{n^{2} + 3n + 2}{2}  \]

 

\[ = \frac{(n+2)(n+1)}{2}. \]

Read 1497 times Last modified on Saturday, 08 March 2014 03:37
Login to post comments

NOTRad