Induction

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$;
• beginning…

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

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…

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

Use mathematical induction to prove that for all integers $n\geq 1$, is divisible by $9$.