Induction

Assignment (current)

You can use the following definitions and identities in the problems about binomial coefficients. Here I use the notation "(n choose k)" for binomial coefficients.

• (k choose 0) = 1, for any integer k >= 0
• if i < j, then (i choose j) = 0.
• (n+1 choose i+1) = (n choose i) + (n choose i+1). This holds for n >= i and for both being at least 0. You can see that this identity is true using the following reasoning. We want to choose i+1 items out of a group of n+1. Take the first of the n+1 items, let us call it x. If we choose x as one of the i+1 items, we need to choose n additional items out of the remaining i; that is we will have (n choose i) remaining options for how to end up with i+1 items. If we do not choose x as one of the i+1 items, then we need to choose i+1 items from the remaining n items. So we have the total number of choices as: (n choose i) + (n choose i+1). Note that this identity also shows up in Pascal's Triangle, where two items on a given row are added up to give an item in the next row.

Some problems are from MCS.

Some hints/notes/comments are in italics.

1. Prove a formula. Use induction to prove the first and third identities listed here: https://en.wikipedia.org/wiki/List_of_mathematical_series#Binomial_coefficients_2
   1. Prove that the summation of (n choose k) for k=0 up to n, is equal to 2ⁿ.
      Prove the base case for the smallest n that it is true for. In this case that is n=0. For the inductive step you have to do it in general for n going to n+1. Just showing the next value of n after the base case is not enough. I am asking you to prove this using induction, not using the binomial theorem.
   2. Prove that the summation of (k choose m) for k=0 up to n, is equal to ( (n+1) choose (m+1)).
2. Prove an inequality. MCS Problem 5.5 - prove that 1 + (1/4) + (1/9) + ... + (1/n²) < 2 - 1/n.
   Note - do /not/ use the exact formula for what the LHS is; rather just use induction and algebra. Note that the claim is /not/ true for n=1, so that should not be your base case.
3. Where are given incorrect proofs wrong. Potential problem areas to consider: base case(s), how the base case(s) is/are used, inductive argument.
   I am looking for you to find where precisely in the bad proof the problem is. It is not enough to "just" argue that the claim is wrong - I want to see where in their proof they are wrong. For wrong induction proofs, the most common places to look are: base case does not hold (even though the inductive argument might work), inductive argument would work but assumes more from the base case than was shown.
   1. MCS Problem 5.22, a false claim that every Fibonacci number is even.
   2. MCS Problem 5.7, a false claim that 2 + 3 + ... n = n*(n+1)/2.
4. Prove something geometric, MCS Problem 5.10. Note that both parts (a) and (b) in the problem should be proved by induction. Note that the "length" of a DET in the problem will always be a power of 2 (they double when you make the next larger DET), so for the inductive step you will be going from n (which you assume is a power of 2) and arguing what happens for length 2n.

Other problems that would normally be assigned, but not this time.

• Prove a recursive algorithm is correct.
• Prove a graph property.

Assignment (old)

Some problems are from Mathematics for Computer Science.

1. See the proof related to tiling from the Induction (II) page in the OneNote notes (in the Proofs section). Consider an 8x8 board with the "red" or missing square being the one in the lower right corner. Show how the proof by induction would construct a valid tiling for this board.
2. Consider the formula for a geometric sum. This is given in MCS problem 5.4 and also here on Wikipedia. Study the proof of the formula using induction and practice giving this proof to yourself (on the board, on paper, or in a document). Visit the CS help lab and give a demo of the proof to one of the lab assistants. You will have at most 10 minutes to complete the argument, and if you cannot get it by then you will need to come back and try again another time. If you are able to give the proof properly, the lab assistant will let you know that you have completed it and they will sign off on it in this document.
3. MCS problem 5.2 - finding the problem in an incorrect induction proof for a tiling problem.
4. MCS problem 5.7 - finding the problem in an incorrect induction proof for an arithmetic sum.
5. MCS problem 5.12 - prove the distributive law of intersection over union.
6. MCS problem 5.13 - prove a formula about the area of the Koch snowflake fractal.
7. MCS problem 5.17 - prove a formula about the number of satisfying assignments for a certain logical formula construction.
8. MCS problem 5.23 - determine what is true given certain assumptions.
9. MCS problem 5.28 - determine what is true and prove it using induction, see also problem 5.32.
10. MCS problem 5.31 - a strong induction proof that is a little tricky.

Grading notes

Some overall grading notes based on assignments turned in for those.

• Please make sure your solutions are in the right order when you hand them in - don't make me look through all of your files for each problem.
• Be careful about how you word things with your induction proofs. You /prove/ the base case(s) (oftentimes it is enough to plug in numbers to verify that a formula holds, but sometimes you do have something you need to prove). For the inductive part, you /assume/ the inductive assumption and must /show/ or /demonstrate/ that it works for k+1 or n+1 (you don't /assume/ that it is true for k+1 or n+1).
• The base cases need to be proved (though sometimes the proof for a base case is really just plugging in numbers and verifying that it works).
• You need to have enough explanation for someone to read this, understand it, and be completely convinced. It is not enough to just have a sequence of equations with no explanation.
• For the base cases, you will work out what the base case is, and you need to have a sentence something like - "and this is correct because ...", with the because part depending on the problem. The point is - you don't assume the reader finishes the thought in their mind, you have to finish the thought for them.

And some grading notes particular to each problem.

1. • I gave credit as long as you had a valid tiling and showed how it was built from four 4x4 tilings. I was hoping you would explain it nicely in terms of tracing the induction argument backwards from the 8x8 board, but I gave credit even if you did not explain it this way.
   • Note that there should only be one triomino that goes between the different 4x4 sections, and it should be the one from the induction argument. If you gave a valid 8x8 tiling but one that could not have resulted from the inductive argument, you do not get full credit.
2. • Make sure you visited the lab to demonstrate the proof - that is what this question was asking you to do.
   • Note that as long as you were checked off as okay by the lab I did not look at anything you might have handed in for this problem (some people included the proof in their submission in canvas).
3. • I gave credit as long as you identified a problem in either the statement itself or where that shows up in the bad proof. I really wanted you to find where in the bad proof it was wrong, but as long as you identified why the claim is not true I gave credit.
   • Note that the base case for n=0 /does/ work. Check what the text has for the P(n) statement when it was proved in the chapter, and that does work for n=0. So that is not the problem with the proof.
4. • It is not enough to pick a random value of n and check that the /claim/ does not work for that value of n. You need to look at the /bad proof/ and determine where exactly it is wrong.
   • The base case for n=0 /is/ true, so that is not the problem.
5. • Note that I did not expect you to prove the n=2 case. That is in the text, so I was assuming you should just state that this base case was already proved.
   • You should make use of induction. Some of you gave something for your inductive step that doesn't actually use the inductive assumption - you more or less argued for the inductive claim directly. For this problem you should make it a real induction proof (which ends up being shorter and simpler than trying to argue it without induction).
6. • You need to justify why your formulas are the way they are - length of the side, number of new little triangles, area of the new little triangles, etc.
   • Be careful with your notation. Use the same notation that is used in the book (in terms of what a_n means, s_n, etc.). If you make up new notation (e.g., side length at the n-th iteration) then be consistent with it. If you use notation one way in part of your solution and another way in a different part, then your solution is incorrect (since it is not consistent).
7. • For part a) you need to explain why it works in general, not just for the first few values of n. In general, showing something works for the first few values of n is /not/ a proof.
   • Make sure to check your work - a number of people ended up with an expression for T_{k+1} that is not actually correct.
8. • Note that the range of values for n is 0, 1, 2, 3, ... in this problem.
   • For part a), an item is "true" if the assumption in the part (together with knowing that P(n) -> P(n+3) and that P(5) is true) would imply the conclusion. For part b) remember that we still know that P(n) -> P(n+3) for all n >= 0.
   • For both parts, pay attention to whether n is qualified in what is being asked (e.g., is it asking for all n or just for some).
9. • Like the other problems, this should be a proof - you need to explain and convince the person reading that the statement is true. It is not enough to "just" show your work that you convinced yourself that it works out.
   • Note that you can figure out which ones it will work for by just starting with each value of n=1, n=2, etc. to see which ones work, until you start to see what the answer will be. You still need a proof after that too.
   • The inductive step for this one is a little different. In most of the other induction proofs, we assume up to n and then look at n+1. For the n+1 case we normally make use of the claim for n. For this one, if you are looking at n+1 it makes more sense to use the claim for n+1-4 or n+1-7. Also note that the inductive assumption is /not/ that we can do all integers up to n, because some values of n /cannot/ be done (e.g., 13); rather the inductive assumption will be that all values of n starting from a particular value up to n can be done.
   • It is possible on this problem (and on induction problems in general) to have a claim that is correct, with a correct proof, but that does not include /all/ of the cases that can be done. For example, you might claim that all multiples of 28 work for this problem; that is true, but that does not include /all/ of the ones that work.
10. • Note that the problem is suggesting to use /strong/ induction. With normal induction, if you are trying to show the induction hypothesis for n, you use the assumption it is true for n-1. With strong induction, rather than using the assumption for n-1, you look at some smaller value(s) (e.g., n/3).
    • Note that in your induction arguments, be careful to keep track of what you are assuming about n. If your induction argument only works for n >= 5 (for example) then you would need to check the base cases up to that point.
    • Most ways to do this problem will need some already known inequalities. For example, 1+x <= e**x for all x>=0 (though this is not one that you will need). You can check for these with desmos or some other graphing site/app.