# Exercises - Patterns and Conjectures

1. Conjecture a formula for the sum of the first $n$ Fibonacci numbers. Prove your guess with induction.

2. Conjecture a formula for the product $F_{i-1} \cdot F_{i+1}$, where $F_i$ represents the $i^{th}$ Fibonacci number. Prove your guess with induction.

3. Pascal's triangle can be constructed in the following way. First, we write a bunch of ones along the left and right edges, and then below each pair of adjacent numbers we write their sum.

It is well known that the $n^{th}$ row (where the top row corresponds to $n=0$) yields the coefficients to the terms resulting from expanding $(x+y)^n$.

The Binomial Theorem also gives a way to produce these coefficients, stating that
$$(x+y)^n = x^n + {}_nC_1 x^{n-1} y + {}_nC_2 x^{n-2} y^2 + {}_nC_3 x^{n-3} y^3 + \cdots + {}_nC_{n-1} x y^{n-1} + y^n$$
where ${}_nC_k$ counts the number of ways to choose $k$ objects from a group of $n$ objects, which is given by
$${}_nC_k = \frac{n!}{k! (n-k)!}$$
Why does the Binomial Theorem work?   Can you use it to explain why the technique described for constructing Pascal's triangle yields the same numbers?

4. A pyramid of balls consisting of five "layers" is shown below. Conjecture a formula for the number of balls needed to make a pyramid of $n$ layers. Can you prove your formula holds?

5. The first diagonal of Pascal's triangle is made entirely of ones. The second diagonal lists the natural numbers in order (1, 2, 3, 4, ... ). Is there any significance to the third diagonal (which begins with 1, 3, 6, ...) ? Can you find a pattern to the sequence? What about the sum of the numbers on each row? Is there a pattern? Make some conjectures, and prove them if you can.

6. Find the number of odd numbers on the $2013^{th}$ row of Pascal's triangle by observing a pattern. (For the sake of consistant numbering, presume that the row reading 1, 2, 1 is the second row.)

7. Find a recurrence formula for the number of ways to put $n$ cents in a machine if we use identical nickles, dimes, and quarters. (You may assume $5 \mid n$.)

8. Find $F_{n+1}/F_{n}$ for the first 20 values of $n$. What do you notice? Can you use what you see to produce a way to approximate $F_n$?   What about $F_{n+\alpha}/F_{n}$ for some given $\alpha$ -- can something similar be said about this quotient?

9. In the arts, the golden rectangle, often considered to be the rectangle with the most aesthetically pleasing proportions, has the property that if you remove a square whose edge length matches that of the smallest side of the rectangle (shown in blue below), you are left with a smaller rectangle (shown in red) with the same proportions as the original one. That is to say $(a+b)/a = a/b$.

1. Find the value of $\varphi = a/b$, dubbed the golden ratio.

2. Suppose $\phi = -b/a$. Find the first few powers of $\varphi$ and $\phi$. What can you say about their differences, $\varphi^n - \phi^n$? Make a conjecture and prove it with induction. (Hint: use the second principle of induction)

10. Let $C(n)$ be defined in the following way:

$$C(n)=\left\{ \begin{array}{cl} \frac{n}{2} & \textrm{ if } n \textrm{ even}\\ 3n+1 & \textrm{ otherwise } \end{array} \right.$$

Now suppose a function $f(n)$ satisfies the following two properties: $f(1)=1$ and for $n \neq 1$, $f(n)=f(C(n))$. Find $f(n)$ for $n=1,2,3,\ldots$, until you feel confident in making a conjecture. (Interestingly, if you make the same conjecture most people do -- nobody on the planet knows whether or not it is true.)

◆ ◆ ◆