Skip to main content

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

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