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:
beginning with any upper-case letter other than \(D\) and followed by any valid record identifier of length \(n-1\text{;}\)
beginning with \(1C\text{,}\)\(2K\text{,}\) or \(7J\) and followed by any valid record identifier of length \(n-2\text{;}\) or
beginning with \(D\) and followed by any string of \(n-1\) decimal digits.
Let \(r(n)\) denote the number of valid record identifiers of length \(n\text{.}\) We take \(r(0)=1\) and note that \(r(1) = 26\text{.}\) Find a recursion for \(r(n)\) when \(n\geq 2\) and use it to compute \(r(5)\text{.}\)
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\text{.}\)
3.
Give a recursion for the number \(g(n)\) of ternary strings of length \(n\) that do not contain \(102\) as a substring.
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)\text{.}\)
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\text{.}\)
Hint.
Check your recursion by manually computing \(h(1)\text{,}\)\(h(2)\text{,}\)\(h(3)\text{,}\) and \(h(4)\text{.}\)
6.
Find \(d=\gcd(5544,910)\) as well as integers \(a\) and \(b\) such that \(5544a + 910 b = d\text{.}\)
7.
Find \(\gcd(827,249)\) as well as integers \(a\) and \(b\) such that \(827a+249b = 6\text{.}\)
8.
Let \(a\text{,}\)\(b\text{,}\)\(m\text{,}\) and \(n\) be integers and suppose that \(am+bn=36\text{.}\) What can you say about \(\gcd(m,n)\text{?}\)
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.
Show that for all positive integers \(n\text{,}\)\(7^n-4^n\) is divisible by \(3\text{.}\)
13.
Show that for all positive integers \(n\text{,}\)\(9^n-5^n\) is divisible by \(4\text{.}\)
14.
It turns out that if \(a\) and \(b\) are positive integers with \(a>b+1\text{,}\) then there is a positive integer \(M>1\) such that \(a^n-b^n\) is divisible by \(M\) for all positive integers \(n\text{.}\) 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\text{.}\)
15.
Use mathematical induction to prove that for all integers \(n\geq 1\text{,}\)
Give a proof by induction of the Binomial Theorem (Theorem 2.30). How do you think it compares to the combinatorial argument given in Chapter 2?
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\text{.}\) Use mathematical induction to prove that \(f(n) = 3n^2-n+2\) for all integers \(n\geq 0\text{.}\)
18.
Consider the recursion given by \(f(n) = f(n-1)+f(n-2)\) for \(n\geq 3\) with \(f(1)=f(2)=1\text{.}\) Show that \(f(n)\) is divisible by \(3\) if and only if \(n\) is divisible by \(4\text{.}\)
19.
Suppose that \(x\in\reals\) and \(x>-1\text{.}\) Prove that for all integers \(n\geq 0\text{,}\)\((1+x)^n\geq 1+nx\text{.}\)
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\text{.}\) So if there are \(t\) operations, then \(2^t\ge n!\text{.}\) Now look up Stirling’s approximation for \(n!\) and continue from there.
