<< Chapter < Page Chapter >> Page >

    F<- 2 * 3

    i<- 3 + 1

producing F = 6 and i = 4.

Since i = 4, the while loop is not entered any longer, F = 6 is returned and the algorithm is terminated.

To prove that the algorithm is correct, let us first note that the algorithm stops after a finite number of steps. For i increases one by one from 1 and n is a positive integer. Thus i eventually becomes equal to n.

Next, to prove that it computes n!, we show that after going through the loop k times, F = k ! and i = k + 1 hold. This is a loop invariant and again we are going to use mathematical induction to prove it.

Proof by induction.

Basis Step: k = 1. When k = 1, that is when the loop is entered the first time, F = 1 * 1 = 1 and i = 1 + 1 = 2. Since 1! = 1, F = k! and i = k + 1 hold.

Induction Hypothesis: For an arbitrary value m of k, F = m! and i = m + 1 hold after going through the loop m times.

Inductive Step: When the loop is entered (m + 1)-st time, F = m! and i = (m+1) at the beginning of the loop. Inside the loop,

    F<- m!* (m + 1)

    i<- (m + 1) + 1

producing F = (m + 1)! and i = (m + 1) + 1.

Thus F = k! and i = k + 1 hold for any positive integer k.

Now, when the algorithm stops, i = n + 1. Hence the loop will have been entered n times. Thus F = n! is returned. Hence the algorithm is correct.

Mathematical induction -- second principle

There is another form of induction over the natural numbers based on the second principle of induction to prove assertions of the form ∀x P(x). This form of induction does not require the basis step, and in the inductive step P(n) is proved assuming P(k)   holds for all k<n . Certain problems can be proven more easily by using the second principle than the first principle because P(k) for all k<n can be used rather than just P(n - 1) to prove P(n).

Formally the second principle of induction states that

      if ∀n [ ∀k [ k<n size 12{ rightarrow } {} P(k) ] size 12{ rightarrow } {} P(n) ] , then ∀n P(n) can be concluded.

Here ∀k [ k<n size 12{ rightarrow } {} P(k) ] is the induction hypothesis.

The reason that this principle holds is going to be explained later after a few examples of proof. Example 1: Let us prove the following equality using the second principle:

For any natural number n , 1 + 3 + ... + ( 2n + 1 ) = ( n + 1 )2.

Proof: Assume that 1 + 3 + ... + ( 2k + 1 ) = ( k + 1 )2   holds for all k,   k<n.

Then 1 + 3 + ... + ( 2n + 1 ) = ( 1 + 3 + ... + ( 2n - 1 ) ) + ( 2n + 1 )

= n2 + ( 2n + 1 ) = ( n + 1 )2 by the induction hypothesis.

Hence by the second principle of induction 1 + 3 + ... + ( 2n + 1 ) = ( n + 1 )2   holds for all natural numbers.

Example 2: Prove that for all positive integer n, i = 1 n size 12{ Sum rSub { size 8{i=1} } rSup { size 8{n} } {} } {} i ( i! ) = ( n + 1 )! - 1

Proof: Assume that

1 * 1! + 2 * 2! + ... + k * k! = ( k + 1 )! - 1   for all k,   k<n.

Then 1 * 1! + 2 * 2! + ... + ( n - 1 ) * ( n - 1 )! + n * n!

= n! - 1 + n * n!    by the induction hypothesis.

= ( n + 1 )n! - 1

Hence by the second principle of induction i = 1 n size 12{ Sum rSub { size 8{i=1} } rSup { size 8{n} } {} } {} i ( i! ) = ( n + 1 )! - 1   holds for all positive integers.

Example 3: Prove that any positive integer n, n>1, can be written as the product of prime numbers.

Questions & Answers

hello, I am happy to help!
Shirley Reply
please can go further on polynomials quadratic
Abdullahi
I need quadratic equation link to Alpa Beta
Abdullahi Reply
find the value of 2x=32
Felix Reply
divide by 2 on each side of the equal sign to solve for x
corri
X=16
Michael
Want to review on complex number 1.What are complex number 2.How to solve complex number problems.
Beyan
use the y -intercept and slope to sketch the graph of the equation y=6x
Only Reply
how do we prove the quadratic formular
Seidu Reply
hello, if you have a question about Algebra 2. I may be able to help. I am an Algebra 2 Teacher
Shirley Reply
thank you help me with how to prove the quadratic equation
Seidu
may God blessed u for that. Please I want u to help me in sets.
Opoku
what is math number
Tric Reply
4
Trista
x-2y+3z=-3 2x-y+z=7 -x+3y-z=6
Sidiki Reply
Need help solving this problem (2/7)^-2
Simone Reply
x+2y-z=7
Sidiki
what is the coefficient of -4×
Mehri Reply
-1
Shedrak
the operation * is x * y =x + y/ 1+(x × y) show if the operation is commutative if x × y is not equal to -1
Alfred Reply
An investment account was opened with an initial deposit of $9,600 and earns 7.4% interest, compounded continuously. How much will the account be worth after 15 years?
Kala Reply
lim x to infinity e^1-e^-1/log(1+x)
given eccentricity and a point find the equiation
Moses Reply
12, 17, 22.... 25th term
Alexandra Reply
12, 17, 22.... 25th term
Akash
A soccer field is a rectangle 130 meters wide and 110 meters long. The coach asks players to run from one corner to the other corner diagonally across. What is that distance, to the nearest tenths place.
Kimberly Reply
Jeannette has $5 and $10 bills in her wallet. The number of fives is three more than six times the number of tens. Let t represent the number of tens. Write an expression for the number of fives.
August Reply
What is the expressiin for seven less than four times the number of nickels
Leonardo Reply
How do i figure this problem out.
how do you translate this in Algebraic Expressions
linda Reply
why surface tension is zero at critical temperature
Shanjida
I think if critical temperature denote high temperature then a liquid stats boils that time the water stats to evaporate so some moles of h2o to up and due to high temp the bonding break they have low density so it can be a reason
s.
Need to simplify the expresin. 3/7 (x+y)-1/7 (x-1)=
Crystal Reply
. After 3 months on a diet, Lisa had lost 12% of her original weight. She lost 21 pounds. What was Lisa's original weight?
Chris Reply
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get the best Algebra and trigonometry course in your pocket!





Source:  OpenStax, Discrete structures. OpenStax CNX. Jul 29, 2009 Download for free at http://cnx.org/content/col10768/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Discrete structures' conversation and receive update notifications?

Ask