5 Replies - 30087 Views - Last Post: 21 March 2013 - 06:43 AM Rate Topic: -----

#1 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Introduction to Proofs- Induction and Big-O

Posted 26 May 2012 - 06:53 PM

*
POPULAR

In this tutorial, I will introduce proofs using math induction as well as Big-O proofs. Proof by math induction is a common way to prove theorems in computer science. The idea behind math induction is that it is impossible to verify that all the terms in a set are valid for a given theorem. Therefore, math induction is used to say that if the theorem holds up to an arbitrary value n, then it also holds for the n+1 term. Think about it like a domino effect. Thus it is also important that the set of elements in the domain are ordered.

As with any proof, inductive proofs start with the theorem. For this first proof, let's use the theorem: 2n < n!, for all n >= 4, where n is in the set of natural numbers.

The next step is to verify the base case(s). When this step is reached, it is sometimes necessary to verify more than one base case. When only one base case is necessary, this is called weak induction. When more than one base case is necessary, it is called strong induction. A prime example of when to use strong induction is for recursive sequences with multiple base cases or terms of multiple preceding terms in the definition. The theorem 2n < n! only requires weak induction, however.

Since n = 4 is the first number for which the inequality holds and the theorem allows for weak induction, it is only necessary to verify for n = 4:
24 < 4!
16 < 24, so this inequality holds for n = 4.

The next step is to state the inductive assumption and hypothesis. The inductive assumption is the point in the proof where we assume that the inequality holds true up to some arbitrary value k. The inductive hypothesis states that if the inductive assumption holds, then the theorem can be proven true for the k+1 case.

For our theorem, a good writeup would look like:
I have assumed that the theorem holds true from n = 4, where n is a natural number, up to some arbitrary value k, where k is a natural number (ie., 2k < k!). I will now prove true for the k+1 case (ie., 2k+1 < (k+1)!).

The next step is to actually prove true for the k+1 case.
Consider k+1:
  • By the inductive assumption, we know that 2k < k!
  • I will now multiply both sides by 2, to get: 2 * 2k < 2* k!
  • By the rules of exponents, we can simplify this to: 2k+1 < 2 * k!
  • Because we know that the smallest value in the truth set is k = 4, k must be greater than 2. Therefore, k+1 must also be greater than 2. So the following inequality must also be true: 2k+1 < (k+1) * k!
  • By the definition of a factorial, we can simplify: 2k+1 < (k+1)!


Finally, the conclusion for the proof:
We have assumed that the theorem 2n < n! holds true from n = 4 up to some arbitrary value k, and have proven true for k+1. Therefore, by the principle of math induction, the theorem holds true.


Now let's look at a case where we would use strong induction. The theorem we will prove inductively is that the Fibonacci sequence, defined as:
f0 = 0
f1 = 1
fn = fn-1 + fn-2

is less than 2n, where n is in the set of natural numbers.

Because we have two base cases, we will need to verify these both in our first step. Since there is a recurrence, we will verify a single case of that as well.
n = 0:
f0 = 0 < 20
0 < 1, so the inequality holds.

n = 1:
f1 = 1 < 21
1 < 2, so the inequality holds.

n = 2:
f2 = f1 + f0 < 22
1 + 0 < 4
1 < 4, so the inequality holds.

I have assumed the theorem is true from n = 0, where n is a natural number, up to some arbitrary value k, where k is a natural number (ie., fk < 2k). I will now prove true for the k+1 case (ie., fk+1 < 2k+1).

Consider for k+1:
  • By the inductive assumption, we know that fk+1 = fk + fk-1, which is less than 2k + 2k-1
  • By factoring out 2k from the right hand side of the inequality, we get: fk + fk-1 < 2k(1 + 1/2)
  • Since (1+1/2) < 2, we know that 2k(1+1/2) < 2k(2), meaning that fk + fk-1 < 2k(2) by transitivity.
  • By the rule of exponents, fk + fk-1 < 2k+1


I have assumed that the theorem fn < 2n from n = 0, where n is a natural number, up to k, which is also a natural number, and proven true for k+1. Therefore, by the principle of math induction, the theorem holds for all natural numbers.


Big-O Proofs

I wanted to introduce Big-O in this tutorial because induction is often used as a part of Big-O proofs. This section will not introduce analyzing code snippets to determine which Big-O notation is applicable. Instead, it will focus on mathematical proof. To begin, let's examine the definition of Big-O:

Quote

Given functions f(n) and g(n), f(x) is O(g(n)) if and only if there exist constants C and k in the set of positive integers such that the following inequality holds: |f(x)| <= C * |g(x)|, for all x >= k, where x is in the set of positive integers.


So in other words, Big-O represents the upper bounds of a function. When writing Big-O proofs, the goal is to satisfy the definition. So we need to find constants k and C so the inequality is satisfied. Solving for k is usually where the induction comes in. Let's look at an example:

Theorem: f(n) = 2n is Big-O g(n) = n!

To prove that 2n is O(n!), we need to show that there exist constants C and k in the set of positive integers such that |2x| <= C * |x!|, for all x >= k, where x is in the set of positive integers.

At this point, an inductive proof will be used to find and verify the k value. We already proved this theorem above, but I will include it below in spoiler tags:
Spoiler


So we have that k = 4, and we will let C = 1. So that leaves us with:
|2x| <= 1 * |x!|, for all x >= 4, where x is a positive integer. We have proven that this inequality holds using induction. Therefore, we have satisfied the definition that f(n) is O(g(n)).

Is This A Good Question/Topic? 7
  • +

Replies To: Introduction to Proofs- Induction and Big-O

#2 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1954
  • View blog
  • Posts: 4,055
  • Joined: 11-December 07

Re: Introduction to Proofs- Induction and Big-O

Posted 29 May 2012 - 02:50 AM

Thanks for the tutorial. Proof by induction is something I always meant to read up on but never had. It isn't in the school maths curriculum in Scotland, and all the maths classes I did at uni were geared towards calculus or numerical methods.
Was This Post Helpful? 0
  • +
  • -

#3 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 198
  • Posts: 1,688
  • Joined: 13-March 10

Re: Introduction to Proofs- Induction and Big-O

Posted 29 May 2012 - 04:28 AM

Proof by induction is part of Advanced Higher Math curriculum.
Was This Post Helpful? 0
  • +
  • -

#4 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1954
  • View blog
  • Posts: 4,055
  • Joined: 11-December 07

Re: Introduction to Proofs- Induction and Big-O

Posted 29 May 2012 - 05:24 AM

Sounds like a good thing. Did they introduce it with the switch from Revised Higher to Higher Still? I was in the last year of Revised Higher. If it was in the curriculum back then, I don't remember my teacher ever mentioning it in class.
Was This Post Helpful? 0
  • +
  • -

#5 alison.lowndes  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 21-March 13

Re: Introduction to Proofs- Induction and Big-O

Posted 21 March 2013 - 06:25 AM

This so helpful TY very much but would you use proof by contradiction to prove n! is not O(2^n)?

This post has been edited by macosxnerd101: 21 March 2013 - 06:39 AM
Reason for edit:: No need to quote the entire post

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Introduction to Proofs- Induction and Big-O

Posted 21 March 2013 - 06:43 AM

I would just use direct proof. Because 2^n is O(n!) and the induction proof shows that n! > 2^n starting at n = 4, n! cannot be 2^n.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1