MAT511 homework,         due Oct 15, 2003

1. Let $a_1=2$, $a_2=4$, and $a_{n+2} = 5a_{n+1} - 6a_n$ defines $a_k$ for all $k \ge 3$. Prove that $a_n = 2^n$ for all natural numbers $n$.

2. Use the well-ordering principle (every subset of ${\mathbb{N}}$ has a least element) to construct a proof that for all natural numbers $a$ and $b$, $b\ne a+b$. Use only the basic axioms of ${\mathbb{N}}$. That is, don't assume that you can just subtract $b$ from both sides. (Hint: suppose that for some $a$ there is a $b$ such that $b=a+b$. By the well-ordering principle, there is a least $a_0$ for which it holds. Now apply the principle again.)

3. In 1202, Leonardo Fibonacci (1170-1250) posed the following famous problem: Suppose a particular breed of rabbit breeds a new pair of rabits each month, except that a 1-month old pair is too young to breed. Suppose further that no rabbit breeds with any other except its paired mate, and that rabbits live forever.

   Then at 1 month, we have our original pair of rabbits.

   At 2 months, we have the original pair (and their offspring, which are too young to breed).

   At three months, we will have two breeding pairs.

   At four months, we will have three pairs.

   At five months, there are five pairs.

   At the $n$th month, we will have $f_n$ pairs of rabbits, given by the inductive sequence

   $$f_1=1, \qquad f_2 = 1, \qquad f_n = f_{n-1} + f_{n-2}$$
   for all natural numbers $n \ge 3$. The $f_n$ are the well-known Fibonacci numbers, which arise in many other contexts besides breeding rabbits.

   Use complete induction to show that for any natural number $a$,

   $$f_a f_n + f_{a+1} f_{n+1} = f_{a+n+1}$$
   for all natural numbers $n$.
4. There are only 12 four-digit numbers that can be formed using exactly the digits 1, 3, 3, and 7, which is less than $4!$, because the two 3's are indistinguishable. Prove that the number of permutations of $n$ objects, $m$ of which are alike, is $n!/m!$.
5. What is the coefficient of $a^3 b^{10}$ in $(a+b)^{13}$?
6. What is the coefficient of $a^2 b^{10}$ in $(a+2b)^{12}$?