## Exercises3.11Exercises

###### 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:

• 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.

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

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

###### 10.

Show that for all integers $$n\geq 4\text{,}$$ $$2^n \lt n!\text{.}$$

###### 11.

Show that for all positive integers $$n\text{,}$$

\begin{equation*} \sum_{i=0}^n 2^i = 2^{n+1}-1. \end{equation*}
###### 12.

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{,}$$

\begin{equation*} n^3 + (n+1)^3 + (n+2)^3 \end{equation*}

is divisible by $$9\text{.}$$

###### 16.

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.