Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /homepages/11/d274290037/htdocs/serabe/wp-content/plugins/jetpack/_inc/lib/class.media-summary.php on line 77

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /homepages/11/d274290037/htdocs/serabe/wp-content/plugins/jetpack/_inc/lib/class.media-summary.php on line 87
Simple mathematical concepts I: Induction. | Conecto ergo sum.
Warning: Use of undefined constant user_level - assumed 'user_level' (this will throw an Error in a future version of PHP) in /homepages/11/d274290037/htdocs/serabe/wp-content/plugins/ultimate-google-analytics/ultimate_ga.php on line 524

Warning: count(): Parameter must be an array or an object that implements Countable in /homepages/11/d274290037/htdocs/serabe/wp-includes/post-template.php on line 284

Warning: Use of undefined constant user_level - assumed 'user_level' (this will throw an Error in a future version of PHP) in /homepages/11/d274290037/htdocs/serabe/wp-content/plugins/ultimate-google-analytics/ultimate_ga.php on line 524

Simple mathematical concepts I: Induction.


Warning: Use of undefined constant user_level - assumed 'user_level' (this will throw an Error in a future version of PHP) in /homepages/11/d274290037/htdocs/serabe/wp-content/plugins/ultimate-google-analytics/ultimate_ga.php on line 524

New equals sign
After reading this and this I realized something is really, really wrong about mathematical concepts out there. Proof by induction is a really, really simple yet powerful proof method.  In this post, I will talk about induction for natural numbers.

Induction is based on two steps, usually called basis and inductive step. I will proof that 1+2+…+n=n(n+1)/2  for all natural numbers using induction.

  1. Basis or base case consists on proving the predicate for an initial value, usually a small one. In the example 1=1*2/2=1.
  2. Inductive step consists on supposing the if the predicate holds for n, then it also holds for n+1. In the example:

1+2+…+n+(n+1)=(n+1)+n(n+1)/2 because we supposed that predicate held for n. We need to prove that this expression is equivalent to (n+1)(n+2)/2. Indeed,

(n+1)+n(n+1)/2=(n+1)(1+n/2)=(n+1)((2+n)/2)=(n+1)(2+n)/2

so the predicate has been proofed for all natural numbers.

Why does induction work?

Think of any natural number, as big as you want. Got it? We know that the predicate holds for 1, and that if the predicate holds for a number it holds for its successor. So it holds for 2, and for 3 and so on until it reach your number.

Other types of induction.

There are several types of inductions. Two of these types are structural induction and complete induction.

Creative Commons License photo credit: hartboy

Leave a Comment


Warning: Use of undefined constant user_level - assumed 'user_level' (this will throw an Error in a future version of PHP) in /homepages/11/d274290037/htdocs/serabe/wp-content/plugins/ultimate-google-analytics/ultimate_ga.php on line 524

Warning: Use of undefined constant user_level - assumed 'user_level' (this will throw an Error in a future version of PHP) in /homepages/11/d274290037/htdocs/serabe/wp-content/plugins/ultimate-google-analytics/ultimate_ga.php on line 524