Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can someone explain Mathematical Induction (to prove a recursive method)

Tags:

math

recursion

Can someone explain mathematical induction to prove a recursive method? I am a freshmen computer science student and I have not yet taken Calculus (I have had up through Trig). I kind of understand it but I have trouble when asked to write out an induction proof for a recursive method.

like image 607
Josh Curren Avatar asked May 14 '09 23:05

Josh Curren


People also ask

How is mathematical induction related to recursion?

Mathematical induction and strong induction can be used to prove results about recursively defined sequences and functions. Structural induction is used to prove results about recursively defined sets. Examples: Defining the factorial function recursively: F(0) = 1, F(n) = n × F(n − 1), for n ≥ 1.

Is mathematical induction the same as recursion?

Recursion is the process in which a function is called again and again until some base condition is met. Induction is the way of proving a mathematical statement. 2. It is the way of defining in a repetitive manner.

How do you prove something by mathematical induction?

The trick used in mathematical induction is to prove the first statement in the sequence, and then prove that if any particular statement is true, then the one after it is also true. This enables us to conclude that all the statements are true.


1 Answers

Here is a explanation by example:

Let's say you have the following formula that you want to prove:

sum(i | i <- [1, n]) = n * (n + 1) / 2

This formula provides a closed form for the sum of all integers between 1 and n.

We will start by proving the formula for the simple base case of n = 1. In this case, both sides of the formula reduce to 1. This in turn means that the formula holds for n = 1.

Next, we will prove that if the formula holds for a value n, then it holds for the next value of n (or n + 1). In other words, if the following is true:

sum(i | i <- [1, n]) = n * (n + 1) / 2

Then the following is also true:

sum(i | i <- [1, n + 1]) = (n + 1) * (n + 2) / 2

To do so, let's start with the first side of the last formula:

s1 = sum(i | i <- [1, n + 1]) = sum(i | i <- [1, n]) + (n + 1)

That is, the sum of all integers between 1 and n + 1 is equal to the sum of integers between 1 and n, plus the last term n + 1.

Since we are basing this proof on the condition that the formula holds for n, we can write:

s1 = n * (n + 1) / 2 + (n + 1) = (n + 1) * (n + 2) / 2 = s2

As you can see, we have arrived at the second side of the formula we are trying to prove, which means that the formula does indeed hold.

This finishes the inductive proof, but what does it actually mean?

  1. The formula is correct for n = 0.
  2. If the formula is correct for n, then it is correct for n + 1.

From 1 and 2, we can say: if the formula is correct for n = 0, then it is correct for 0 + 1 = 1. Since we proved the case of n = 0, then the case of n = 1 is indeed correct.

We can repeat this above process again. The case of n = 1 is correct, then the case of n = 2 is correct. This reasoning can go ad infinitum; the formula is correct for all integer values of n >= 1.

like image 177
Ayman Hourieh Avatar answered Sep 29 '22 18:09

Ayman Hourieh