Mathematical induction assignment
Induction is a proof technique that is useful for proving statements that deal with an infinite number of items in a countable infinity such as integers. For example, consider the following problem:
Prove that for every integer N >= 1, The sum from 1 to N == (N*(N+1)) / 2
How can we prove such a statement is true? It makes a statement about an infinite (countably infinite) number of possibilities. We certainly could not, in finite time, solve each of the infinite equations individually. That is, though we could begin pluggting values in for N such as
P(1) 1 = (1*2)/ 2 is true
P(2) 1+2 = (2*3)/2 = 3 is true
P(3) 1+2+3 = (3*4)/2 = 6 is true
And so on…..
but since there is an infinite set of values that N can take on we would never be able to stop this process and KNOW for certain that there is not an exception somewhere down the line.
NOTE – to disprove statements such as this is a trivial task. That is, since the statement says that the equation holds for ALL possible values of N, all we need to do to disprove it is produce a single example where it fails. So, for example if the problem said “For all integers N >= 1, N divded by 2 produces a remainder of 0” – we could easily disprove it by taking a specific value of N for which the statement is false. For example N = 5 (or any odd integer).
However, we cannot prove such a statement true simply by looking at a single example! If we could, then we could have proved the previous statement as true (which it isn’t) by pointing out that if N = 8 then it does have a 0 remainder when divided by 2. Although this is obviously incorrect, students often attempt to prove statements about countably infinite sets in such a manner – it is known as an “Attempt to prove by example” and it is simply incorrect and causes math and science professors to have strokes and give poor grades.
The solution to our problem is known as mathematical induction or simply “induction”. It is a fairly simple process to understand though it can, at times, appear to be “proof by magic”. To understand how it works, consider an infinite collection of dominoes lined up one after the other. To show that we can knock them all over we would begin by directly proving that we can knock over the first domino. By directly proving, we mean that we would use any of the proof techniques studied earlier to show with certainty that the first domino can be knocked over.
The next thing we do is to ASSUME that an arbitrary domino later in the list (Let’s call it domino k) can be knocked down and then use this assumption to prove directly that domino k+1 must also fall. IF we can use our assumption that domino k falls to prove domino k+1 must also fall, then we can combine this fact with the fact that we can knock over the first to prove that all of the dominoes must fall.
Why? Because, we have shown that we can directly knock over the first and if we let k = 1 then we know k+1 = 2 must fall – BUT that means if k = 2 then k+1 = 3 must fall as well and so on and so on.
To see how this would work on our initial problem we will examine an inductive proof.
Problem : For every integer N >= 1, The sum from 1 to N == (N*(N+1)) / 2
We begin our inductive proof by proving what is known as the “base case”. This is equivalent to our concept of proving that we can knock down our first domino. Since our proof indicates that we are solving for all integers >= 1, our base case requires that we prove the problem statement with N == 1). This is usually trivial in most cases as it is with this problem. We simply plug in 1 for N and easily show that the equation holds.
P(1): 1 = (2*1)/2 = 2/2 = 1. BASE CASE
The next step in an inductive proof is to ASSUME that we can solve our problem for some arbitrary value of N (we often refer to it as the value k) and then show that this assumption can be used to prove that the statement holds for the value k+1 as well. This assumption is known as the “inductive hypothesis”.
P(k): ASSUME that 1+2+3+…+k = (k*(k+1))/2. INDUCTIVE HYPOTHESIS
Next, we must show that P(k+1) is true by using our inductive hypothesis at some point. This is known s the “inductive step”. Note that it is essential that we prove P(k+1) using our inductive hypothesis. This has the effect of showing that if one domino falls then the next one will necessarily fall as well. We simply plug in the value k+1 for N in our problem and use standard proof techniques/rules to solve the problem BUT note that we can use our assumption of the validity of P(k).
Show P(k+1). That is prove that 1+2+3+…+k+(k+1) = ((k+1)*(k+2))/2
1+2+…+k+(k+1) = [1+2+….+k] + (k+1) by Associativity of addition
= (k*(k+1))/2 + (k+1) by our Inductive Hypothesis!!!!
= [(k*(k+1)) + 2*(k+1)] / 2 by finding a common denominator
= [k2 + 3k + 2] / 2 by algebra
= [(k+1)*(k+2)] / 2 by factoring
End of proof.
Note the second step in our proof of P(k+1). This is our inductive step. It is where we apply our inductive hypothesis P(k) to the proof. By replacing part of our equation with the right hand side of our hypothesis we were able, with relatively simple algebra, to solve P(k+1).
As shown in the previous example, inductive proofs take a specific form.
Base case P(1). – prove it directly. Usually it is trivial to do so.
Assume P(k)
Show P(k+1) – do this by applying the right-hand side of the inductive hypothesis at some point in the proof and using standard proof techniques and algebra.
Example 2
Problem P: For N >= 4, 2N >= N2
Proof by induction on N.
Base P(4): 24 = 16 >= 42
Note that in this example, our base case is not 1 but rather 4. In fact, the given equation does not hold for N=1,2, or 3 which is why it was written for all N >= 4.
Assume P(k): 2k >= k2.
Show P(k+1) : 2k+1 >= (k+1)2
2k+1 = 2 * 2k by rules of multiplication and exponents
>= 2 * k2 inductive step – by applying our inductive hypothesis assumption
Note that in our inductive step above we went from using an = to using >=. This is because of the application of our inductive hypothesis. We replaced 2k by k2 which, by the assumption is <= 2k.
>= (k+1)2 for k >= 4. End of proof.
Example 3
Problem P: For alln>1, 8n – 3n is divisible by 5.
Base Case P(1): 81 – 31 = 8 – 3 = 5, which is clearly divisible by 5.
Assume, P(k): 8k – 3k is divisible by 5.
Show P(k+1): 8k+1 – 3k+1 is divisible by 5.
8k+1 – 3k+1 = 8k+1 – 3×8k + 3×8k – 3k+1 since adding X and subtracting X has no effect. In this case we subtract 3×8k as well as add it so it does not change the final value.
= 8k(8 – 3) + 3(8k – 3k) by factoring/algebra
= 8k(5) + 3(8k – 3k) by subtraction
The first term in 8k(5) + 3(8k – 3k) has 5 as a factor (explicitly), and the second term is divisible by 5 (by our inductive hypothesis!). Since we can factor a 5 out of both terms, then the entire expression, 8k(5) + 3(8k – 3k) = 8k+1 – 3k+1, must be divisible by 5.
End of proof.
Strong induction
The form of induction we have looked at so far is known as weak induction. This means that when we attempt to prove P(k+1) we can only use our base case and our inductive hypothesis P(k) to assist in our proof.
It turns out that we can actually strengthen our assumption so that we do not only assume that P(k) is true but can also assume that our hypothesis holds for ALL values less than k+1. Thus we can assume P( ) is true for P(k), but also for P(k-1), P(k-2) and so on right down to our base case.
Although this is not always necessary, it can make a number of proofs much easier.
Example 4
Problem P: All integers N >= 2 are divisible by a prime number.
Base P(2) – trivial as 2 is a prime and ths divisible by itself.
Assume for ALL values x, such that 2 <= x < k+1, P(x) is true.
Show P(k+1) is true.
k+1 is either prime or it is not. If it is prime then it is obviously divisible by itself and thus P(k+1) is true.
If k+1 is not prime then it must be a composite number meaning k+1 = A * B.
Note that A and B must be >= 2 and also < k+1.
So, 2 <= A < k+1.
By our inductive hypothesis, we can assume that P(A) is true and thus A is divisible by some prime number q. Since q divides A and A divides k+1, we know by transitivity that q divides k+1.
The above argument holds for B as well but it is not necessary. We showed that a prime number q divides k+1.
Note how the strong induction allowed us to use an A that was anywhere from our base case to P(k).
Structural Induction
Induction is also used to prove things about certain types of structures. In particular, if a data structure, say a tree, is defined recursively then induction can often be used to prove properties for a tree.
A Tree can be defined recursively (NOTE: Recursion and induction are the same fundamental principle!!!!) as follows:
A Tree is: a. A single node (root) OR >=2 trees connected to a root node. End of recursive definition!
Base case : A single node is a tree and that node is the ROOT of the tree.
Induction/Recursion If T1, T2, T3, …., Tk are all trees then we can build a new tree by creating a new node N as the root of the tree and adding edges from N to the roots of the trees T1,T2,T3….Tk.
Example 5
Problem: Prove that every tree has exactly one more node than it has edges.
Our induction will be on the number of nodes in the tree.
Base P(1) : A tree with one node has no edges so this is trivially true.
Assume P(x) for 1 <= x <= k : A tree with x nodes has x-1 edges. STRONG
Inductive hypothesis
Show P(k+1) : A tree with k+1 nodes has k edges.
All trees have a unique root node. This means that our tree with k+1 nodes has such a root. This root must be connected to k different trees via k edges. If we temporarily remove the root node and all k edges connecting it to the k subtrees we are left with k trees. Since each of them must be smaller than k+1 we know the inductive hypothesis holds. This means that for each of the k subtrees, there is one more node than edges.
This means that taken together we have k more nodes than edges among the k trees right? Now let’s add back what we took out earlier. First we will add back the root. This means that we have k+1 more nodes than edges. Now we connect the root to the roots of the k subtrees and thus we add k edges. This gives us (k+1) – k = 1. and we are done.
A word of warning. There are some common mistakes people make when using induction.
Proving the wrong base case.
Sounds stupid but it can easily happen. Be careful not to “prove” something for a base case it does not truly hold for.
Proving nothing in the induction.
Again, sounds silly but I see a lot of cases where students, when they get to the final step, state what they are trying to prove P(k+1) and then start with the left hand side of an equation. They follow it with line after line of algebraic manipulation and end up “proving” the left hand side of the equation! Sort of like walking in circles.
Failing to apply the inductive hypothesis
It is very likely that your proof is wrong if you never, in fact, use the inductive hypothesis. It is essential to the concept of inductive proofs.
Examples of using induction to design an algorithm….
- Sorting – OK we know this one but suppose we didn’t….
Given a list of N numbers sort them
BASE: We can sort N numbers for N==1. Trivial a one element list is, by definition, sorted.
ASSUME we can sort a list of size k == N-1 numbers.
Show for p(N) - We don’t know how to sort a list of length N so let’s turn it into a smaller list – perhaps one of length N-1. How? Strip off an element – say the last one in the list. What remains? A list of length N-1 right? But by the IH we can sort that! So do it. Now, we have a sorted list of N-1 elements and that last element we stripped off.
Now we look for a simple way to combine them. Easy right? Just swap it down the list one element at a time until we find its correct position. So the resulting algorithm looks something like
{`
[ ] Sort( list [ ], length )
{
If (length == 1) return list
Else
Sortlist = sort( list[ ], length – 1 )
Pos = length
While ( Pos > 1 ) && ( Sortlist[Pos – 1] > Sortlist[POS] )
Swap ( Sortlist[pos], Sortlist[Pos -1])
Pos—
Return( Sortlist[])
}
`}
What is it? The insertion sort! Not a great solution (unless list is close to sorted to begin with) but it works.
NOTE – we chose to reduce the list by one element – that last one – Could we have selected differently? Sure – induction doesn’t care which element we choose just that we reduce the size of the list. So suppose instead of just taking the last element we took say the largest element out? The induction-approach would say
Remove the largest – sort the remaining and place the largest in the last spot! Done. This, of course is the pathetic Selection sort which always sucks.
BUT NOTE – we have been only exploring weak induction. Perhaps strong induction would work. This means we don’t always have to reduce the problem by one – we could reduce it to 2 smaller versions and rely on strong induction.
IH – we can sort a list < N elts. Now, when given a list of size N we will break it in half (roughly) and can assume that both can be sorted via our IH!!!! So – given a list of size N we split it in half – sort both halves (using the IH) and then need only combine the two sorted lists? How – pretty easy right just merge them together.Obviously this results in the Merge sort algorithm which is quite an improvement.
The problems we deal with can come from all areas of computing. For example consider the following graphics-related problem.
Given a 2D plane and a collection of N lines dividing the plane into regions color the regions using only blue and red so that no two neighboring regions are the same color.
Our induction will be on the number of lines.
BASE CASE – 1 line. Results in two regions color one red and one blue – done.
ASSUME it works for k <= N lines.
Color the regions for N lines. How? WE don’t know right? Well reduce the number of lines!!!! Take one out, now we have N-1 lines. OK well our IH says we can do it so do it! Now we need to figure out how to take our solution for N-1 lines and add the Nth line and color the resulting regions? Any ideas?
Celebrity Problem
You have a room with N people in it. One of them is a celebrity. A celebrity is defined as an individual who is known by everyone else in the room but does not know anyone there. Your task is to identify the celebrity by asking only questions of the form “Excuse me person X do you know person Y over there?”
Now I think we could all come up with a solution pretty quickly but can we improve on it via induction? I mean one way is to ask all N people if they know the other N-1 people and keep track of the answers and thus identify the celebrity when we are done. That is like N*N-1 total questions and thus O(N^2).
Let’s try induction….
Base – trivial
Assume we can identify celeb in room of <N people.
Given room with N what do we do? Select one to leave out. Identify the celeb if one exists of the remaining N-1 people. 3 possibilities
- The celeb is found from the N-1.
- The person we left out is the celeb
- No celeb in the room.
Case a trivial – just ask the potential celeb if they know person N (answer is no) and person N if they know the celeb (answer yes) then we confirm the celeb.
Case b oops….. now we have problems….. we’d have to go through everyone asking 2 questions each…… yuck….. we’re back to our O(N^2) algorithm….
Hmmm….. OK but let’s ask if we can reduce the problem in a different manner than simply grabbing someone at random and removing them….. OK – who do we wish to pull out???? Obviously NOT the celebrity because that caused us problems – we want to remove a non-celebrity….doesn’t matter which but we want one…. How do we find one EASILY?
