Induction: exercises

Practice (25)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. A database uses record identifiers that are alphanumeric strings in which the \(10\) decimal digits and \(26\) upper-case letters are valid symbols. The criteria that define a valid record identifier are recursive. A valid record identifier of length \(n\geq 2\) can be constructed in the following ways:

   • \(D\)\(n-1\)
   • \(1C\)\(2K\)\(7J\)\(n-2\)
   • \(D\)\(n-1\)

   Let \(r(n)\) denote the number of valid record identifiers of length \(n\). We take \(r(0)=1\) and note that \(r(1) = 26\). Find a recursion for \(r(n)\) when \(n\geq 2\) and use it to compute \(r(5)\).

   ഉത്തരം വെളിപ്പെടുത്തുക

   The problem gives us the initial values, assuming \(r(0) = 1\). The first bullet gives us \(25 r(n - 1)\) identifiers, since the first position is any of 25 letters and then \(r(n - 1)\) record identifiers follow. The second bullet gives \(3 r(n - 2)\) record identifiers, since the first positions are 1C, 2K, or 7J, and then \(r(n - 2)\) identifiers of length \(n - 2\) can follow. The third bullet is not recursive and has \(10^{n-1}\) options since the record identifier must start with D and then there are 10 choices for each of the remaining \(n - 1\) positions. The recurrence is therefore \(r(n) = 25r(n-1) + 3r(n-2) + 10^{n-1}\) for \(n\geq 2\) with \(r(0) = 1\) and \(r(1) = 26\). We can compute that \(r(2) = 25 r(1) + 3 r(0) + 10 = 663\), \(r(3) = 25 r(2) + 3 r(1) + 10^{2} = 16753\), \(r(4) = 25 r(3) + 3 r(2) + 10^{3} = 421,814\), and \(r(5) = 25 r(4) + 3 r(3) + 10^{4} = 10,605,609\).

2. Consider a \(1\times n\) checkerboard. The squares of the checkerboard are to be painted white and gold, but no two consecutive squares may both be painted white. Let \(p(n)\) denote the number of ways to paint the checkerboard subject to this rule. Find a recursive formula for \(p(n)\) valid for \(n\geq 3\).

3. Give a recursion for the number \(g(n)\) of ternary strings of length \(n\) that do not contain \(102\) as a substring.

   ഉത്തരം വെളിപ്പെടുത്തുക

   We begin by determining the initial values. No string of length less than \(3\) can contain \(102\), so \(g(1) = 3\) and \(g(2) = 9\). For length \(3\), the only string we must exclude is \(102\) itself, so \(g(3) = 3^{3}=27-1=26\). We now analyze the situation where we have a string of length \(n\gt 3\). If the first position in the string is \(0\), then the remaining \(n-1\) positions can be filled by any string of length \(n-1\) that does not contain \(102\), of which there are \(g(n-1)\). The situation is identical when the first position is \(2\). Thus, we need to consider how many options there are when the first position is \(1\). In this case, we can fill the remaining \(n-1\) positions with any string that does not contain \(102\) and does not start with \(02\). To count these strings, we count the strings of length \(n-1\) not containing \(102\) by using \(g(n-1)\) and subtract those that start with \(02\). Thus, we are considering a string of length \(n-1\) in which the first two positions are \(02\), so the remaining string has length \(n-3\). Since the second position is a \(2\), we can fill those remaining positions with any string of length \(n-3\) that does not contain \(102\). There are \(g(n-3)\) such strings. This is the count we needed to subtract, so we have \(g(n-1)-g(n-3)\) strings of length \(n-1\) that start with \(1\) and do not contain \(102\). Putting this all together, we have \(g(1)=3\), \(g(2)=9\), \(g(3)=26\), and for \(n\geq 4\), \(g(n) = 3g(n-1) - g(n-3)\).

4. A \(2\times n\) checkerboard is to be tiled using two types of tiles. The first tile is a \(1\times 1\) square tile. The second tile is called an \(L\)-tile and is formed by removing the upper-right \(1\times 1\) square from a \(2\times 2\) tile. The \(L\)-tiles can be used in any of the four ways they can be rotated. (That is, the missing square can be in any of four positions.) Let \(t(n)\) denote the number of tilings of the \(2\times n\) checkerboard using \(1\times 1\) tiles and \(L\)-tiles. Find a recursive formula for \(t(n)\) and use it to determine \(t(7)\).

   ഉത്തരം വെളിപ്പെടുത്തുക

   There is one option for \(n=1\), when we can only use two \(1\times 1\) tiles. For \(n=2\), there are 5 options: use four \(1\times 1\) tiles or position an \(L\)-tile in one of four ways and then place a \(1\times 1\) tile in the remaining position. For \(n=3\), there are 11 options: two ways to use two \(L\)-tiles, one way to use only \(1\times 1\) tiles, and each of the cases for \(n=2\) that uses an \(L\)-tile leads to two options for \(n=2\) by placing a column of \(1\times 1\) tiles on either side of the case from \(n=2\).

   To find the recursion, imagine a \(2\times n\) checkerboard with all but the leftmost 1, 2, or 3 columns covered. We do this in such a way that no tile is partially covered, so the only way to do this with only one column uncovered is two \(1\times 1\) tiles and then \(t(n-1)\) ways to tile the rest. Moving to two columns, we don't need to think about four \(1\times 1\) tiles because that would have been counted when only one column was covered. Thus, we have just the four configurations of a \(1\times 1\) and an \(L\)-tile, so \(4t(n-2)\) ways. Finally, if we need to uncover 3 columns, there are \(2t(n-2)\) options because we must have two \(L\)-tiles. Thus, we have \[\begin{aligned}\end{aligned}\] for \(n\geq 4\), with \(t(1) = 1\), \(t(2) = 5\), and \(t(3) = 11\).

5. Let \(S\) be the set of strings on the alphabet \(\{0,1,2,3\}\) that do not contain \(12\) or \(20\) as a substring. Give a recursion for the number \(h(n)\) of strings in \(S\) of length \(n\).

   ഉത്തരം വെളിപ്പെടുത്തുക

   Hint:

   Check your recursion by manually computing \(h(1)\), \(h(2)\), \(h(3)\), and \(h(4)\).

6. Find \(d=\gcd(5544,910)\) as well as integers \(a\) and \(b\) such that \(5544a + 910 b = d\).

7. Find \(\gcd(827,249)\) as well as integers \(a\) and \(b\) such that \(827a+249b = 6\).

8. Let \(a\), \(b\), \(m\), and \(n\) be integers and suppose that \(am+bn=36\). What can you say about \(\gcd(m,n)\)?

9. (A challenging problem) For each formula, give both a proof using the Principle of Mathematical Induction and a combinatorial proof. One of the two will be easier while the other will be more challenging.

   1. \(\displaystyle 1^2+2^2+3^2+\dots+ n^2= \frac{n(n+1)(2n+1)}{6}\)

   2. \(\displaystyle\binom{n}{0}2^0+\binom{n}{1}2^1+\binom{n}{2}2^2+\dots+\binom{n}{n}2^n=3^n\)

   ഉത്തരം വെളിപ്പെടുത്തുക

   Here is an induction proof of the first statement. We will prove this by induction. The basis step is when \(n=1\). Here the left-hand side is \(1^{2} = 1\). The right-hand side is \(\displaystyle\frac{1(1+1)(2\cdot 1+1)}{6}= \frac{6}{6}= 1\). Thus, the basis step is proved.

   Now assume that for some integer \(k\geq 1\) that \(\displaystyle 1^{2}+2^{2}+3^{2}+\dots+ k^{2}= \frac{k(k+1)(2k+1)}{6}\). We will prove that \(\displaystyle 1^{2}+2^{2}+3^{2}+\dots+ k^{2} + (k+1)^{2}= \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}\). We work from the left-hand side, where we can use the induction hypothesis to replace the first \(k\) terms: \[\begin{aligned}1^{2}+2^{2}+3^{2}+\dots+ k^{2} + (k+1)^{2}\amp= \frac{k(k+1)(2k+1)}{6}+ (k+1)^{2}= \frac{k(k+1)(2k+1)}{6}+ \frac{6(k+1)^{2}}{6} \\ \amp= \frac{k(k+1)(2k+1)+6(k+1)^{2}}{6}= \frac{(k+1)(k(2k+1)+6(k+1)}{6} \\ \amp= \frac{(k+1)(2k^{2}+k+6k+6}{6}= \frac{(k+1)(2k^{2}+7k+6}{6} \\ \amp= \frac{(k+1)(k+2)(2k+3)}{6}= \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}\end{aligned}\]. Therefore, by the Principle of Mathematical Induction, for all positive integers \(n\), \(\displaystyle 1^{2}+2^{2}+3^{2}+\dots+ n^{2}= \frac{n(n+1)(2n+1)}{6}\).

10. Show that for all integers \(n\geq 4\), \(2^n \lt n!\).

11. Show that for all positive integers \(n\), \[\begin{aligned}\end{aligned}\]

12. Show that for all positive integers \(n\), \(7^n-4^n\) is divisible by \(3\).

13. Show that for all positive integers \(n\), \(9^n-5^n\) is divisible by \(4\).

14. It turns out that if \(a\) and \(b\) are positive integers with \(a>b+1\), then there is a positive integer \(M>1\) such that \(a^n-b^n\) is divisible by \(M\) for all positive integers \(n\). Determine \(M\) in terms of \(a\) and \(b\) and prove that it is a divisor of \(a^n-b^n\) for all positive integers \(n\).

15. Use mathematical induction to prove that for all integers \(n\geq 1\), \[\begin{aligned}\end{aligned}\] is divisible by \(9\).

    ഉത്തരം വെളിപ്പെടുത്തുക

    Proof

    We will prove this by induction. The basis step is when \(n=1\). In this case, we have \(1^{3}+2^{3}+3^{3} = 1+8+27 = 36 = 9\cdot 4\). This shows that the sum is divisible by \(9\) as required.

    Now suppose that for some integer \(k\geq 1\) that \(k^{3}+(k+1)^{3}+(k+2)^{3}\) is divisible by \(9\). That is, there exists an integer \(m\) so that \(k^{3}+(k+1)^{3}+(k+2)^{3} = 9m\). We now consider \((k+1)^{3}+(k+2)^{3}+(k+3)^{3}\) and expand only the last term. This gives us \[\begin{aligned}\end{aligned}\]. By the induction hypothesis, the first three terms are equal to \(9m\), so now we have \(9m+9k^{2} + 27k+27 = 9(m+k^{2}+3k+3)\). Since \(m\) and \(k\) are integers, \(m+k^{2}+3k+3\) is an integer as well. Therefore, \((k+1)^{3}+(k+2)^{3}+(k+3)^{3}\) is divisible by \(9\).

    By the Principle of Mathematical Induction, for all integers \(n\geq 1\), \[\begin{aligned}\end{aligned}\] is divisible by \(9\).

16. Give a proof by induction of the Binomial Theorem (). How do you think it compares to the combinatorial argument given in ?

17. Consider the recursion given by \(f(n) = 2f(n-1) - f(n-2) + 6\) for \(n\geq 2\) with \(f(0)=2\) and \(f(1)=4\). Use mathematical induction to prove that \(f(n) = 3n^2-n+2\) for all integers \(n\geq 0\).

18. Consider the recursion given by \(f(n) = f(n-1)+f(n-2)\) for \(n\geq 3\) with \(f(1)=f(2)=1\). Show that \(f(n)\) is divisible by \(3\) if and only if \(n\) is divisible by \(4\).

19. Suppose that \(x\in\reals\) and \(x>-1\). Prove that for all integers \(n\geq 0\), \((1+x)^n\geq 1+nx\).

20. Show that there is a positive constant \(c\) so that any algorithm that sorts a sequence of \(n\) positive integers must, in worst case, take \(cn\log n\) steps.

    ഉത്തരം വെളിപ്പെടുത്തുക

    Hint:

    Hint: There are \(n!\) permutations of a set of \(n\) distinct integers. Each operation reduces the number of possibilities by a multiplicative fraction which is at most \(1/2\). So if there are \(t\) operations, then \(2^t\ge n!\). Now look up Stirling's approximation for \(n!\) and continue from there.

21. How many \(k\)-element subsets of \([n]\) contain the number \(1\)?

22. Suppose that \(f\) is a function on the positive integers. You know \[\begin{aligned}\end{aligned}\] as well as \(f(1) = 3\), \(f(2) = 7\), and \(f(4) = 8\). Then \(f(6)\)

23. To prove that \(\displaystyle \sum_{i=1}^n (4i-3) = n(2n-1)\) for all positive integers \(n\), the best first step is which of the following?

24. To prove that \(\displaystyle \sum_{i=1}^n (4i-3) = n(2n-1)\) for all positive integers \(n\), the best next step is which of the following?

25. To prove that \(\displaystyle \sum_{i=1}^n (4i-3) = n(2n-1)\) for all positive integers \(n\), the best next step is which of the following?

നീ സ്വയം ശ്രമിക്ക്.

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

കൂടുതല്‍ Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs