91Ó°ÊÓ

Consider the recurrence relation \(a_{n}=4 a_{n-1}-4 a_{n-2}\). (a) Find the general solution to the recurrence relation (beware the repeated root). (b) Find the solution when \(a_{0}=1\) and \(a_{1}=2\). (c) Find the solution when \(a_{0}=1\) and \(a_{1}=8\).

While the above proof does not work (it better not since the statement it is trying to prove is false!) we can prove something similar. Prove that there is a strictly increasing sequence \(a_{1}, a_{2}, a_{3}, \ldots\) of numbers (not necessarily integers) such that \(a_{n}<100\) for all \(n \in \mathbb{N}\). (By strictly increasing we mean \(a_{n}

A ternary string is a sequence of \(0^{\prime} \mathrm{s}, 1^{\prime} \mathrm{s}\) and \(2^{\prime} \mathrm{s} .\) Just like a bit string, but with three symbols. Let's call a ternary string good provided it never contains a 2 followed immediately by a \(0 .\) Let \(G_{n}\) be the number of good strings of length \(n .\) For example, \(G_{1}=3,\) and \(G_{2}=8\) (since of the 9 ternary strings of length \(2,\) only one is not good). Find, with justification, a recursive formula for \(G_{n},\) and use it to compute \(G_{5}\)

Prove using induction that every set containing \(n\) elements has \(2^{n}\) different subsets for any \(n \geq 1\).

Consider bit strings with length \(l\) and weight \(k\) (so strings of \(l 0^{\prime} \mathrm{s}\) and \(1^{\prime}\) s, including \(k 1^{\prime}\) s). We know how to count the number of these for a fixed \(l\) and \(k .\) Now, we will count the number of strings for which the sum of the length and the weight is fixed. For example, let's count all the bit strings for which \(l+k=11\). (a) Find examples of these strings of different lengths. What is the longest string possible? What is the shortest? (b) How many strings are there of each of these lengths. Use this to count the total number of strings (with sum 11 ). (c) The other approach: Let \(n=l+k\) vary. How many strings have sum \(n=1\) ? How many have sum \(n=2 ?\) And so on. Find and explain a recurrence relation for the sequence \(\left(a_{n}\right)\) which gives the number of strings with sum \(n\). (d) Describe what you have found above in terms of Pascal's Triangle. What pattern have you discovered?

Prove that there is a sequence of positive real numbers \(a_{0}, a_{1}, a_{2}, \ldots\) such that the partial sum \(a_{0}+a_{1}+a_{2}+\cdots+a_{n}\) is strictly less than 2 for all \(n \in \mathbb{N}\). Hint: think about how you could define what \(a_{k+1}\) is to make the induction argument work.

Prove that every positive integer is either a power of \(2,\) or can be written as the sum of distinct powers of 2 .

Let \(t_{n}\) denote the number of ways to tile a \(2 \times n\) chessboard using \(1 \times 2\) dominoes. Write out the first few terms of the sequence \(\left(t_{n}\right)_{n \geq 1}\) and then give a recursive definition. Explain why your recursive formula is correct.

You will prove that the Fibonacci numbers satisfy the identity \(F_{n}^{2}+\) \(F_{n+1}^{2}=F_{2 n+1} .\) One way to do this is to prove the more general identity, $$ F_{m} F_{n}+F_{m+1} F_{n+1}=F_{m+n+1} $$ and realize that when \(m=n\) we get our desired result. Note that we now have two variables, so we want to prove this for all \(m \geq 0\) and all \(n \geq 0\) at the same time. For each such pair \((m, n),\) let \(P(m, n)\) be the statement \(F_{m} F_{n}+F_{m+1} F_{n+1}=F_{m+n+1}\) (a) First fix \(m=0\) and give a proof by mathematical induction that \(P(0, n)\) holds for all \(n \geq 0 .\) Note this proof will be very easy. (b) Now fix an arbitrary \(n\) and give a proof by strong mathematical induction that \(P(m, n)\) holds for all \(m \geq 0\). (c) You can now conclude that \(P(m, n)\) holds for all \(m, n \geq 0 .\) Do you believe that? Explain why this sort of induction is valid. For example, why do your proofs above guarantee that \(P(2,3)\) is true?