| | |
Conjecture a formula for the sum of the first $n$ Fibonacci numbers. Prove your guess with induction.
Letting $F_i$ denote the $i^{th}$ Fibonacci number (where $F_0 = F_1 = 1$), we might conjecture that
$$\sum_{i=0}^n F_i = F_{n+2} - 1$$We can establish this result via induction.
First note that when $n=0$, the left side above is simply $\sum_{i=0}^n F_i = F_0 = 1$, while the right side evaluates to and $F_2 - 1 = 2 - 1 = 1$. As these agree in value, our basis step is complete.
Then, to proceed with the inductive step -- we need to show that if $\sum_{i=0}^k F_i = F_{k+2} - 1$, then $\sum_{i=0}^{k+1} F_i = F_{k+3} - 1$. To this end, consider the following:
$$\begin{array}{rcl} \sum_{i=0}^{k+1} F_i &=& \left[ \sum_{i=0}^k F_i \right] + F_{k+1}\\\\ &=& (F_{k+2} - 1) + F_{k+1}\\\\ &=& (F_{k+2} + F_{k+1}) - 1\\\\ &=& F_{k+3} - 1 \end{array}$$Therefore by the principle of mathematical induction, the following holds for integer values of $n \ge 0$:
$$\sum_{i=0}^n F_i = F_{n+2} - 1$$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.
We conjecture that
$$F_{n-1} \cdot F_{n+1} = F_n^2 + (-1)^{n+1}$$We can prove this via strong induction...
First, we deal with the basis step. When $n=1$, we have $F_0 \cdot F_2 = 1 \cdot 2 = 2$, and $F_1^2 + (-1)^2 = 1 + 1 = 2$. These values being equal, the basis step is established.
Now, we turn our attention to the inductive step.
We need to show that if $F_{n-1} \cdot F_{n+1} = F_n^2 + (-1)^{n+1}$ when $n \le k$, then $F_k \cdot F_{k+2} = F_{k+1}^2 + (-1)^{k+2}$.
To this end, consider the following...
$$\begin{array}{rcl} F_k \cdot F_{k+2} &=& (F_{k-2} + F_{k-1})(F_k + F_{k+1})\\\\ &=& F_{k-1} F_{k+1} + F_{k-1} F_k + F_{k-2} F_k + F_{k-2} F_{k+1}\\\\ &=& \left[ F_k^2 + (-1)^{k+1} \right] + F_{k-1} F_k + \left[ F_{k-1}^2 + (-1)^k \right] + F_{k-2} F_{k+1}\\\\ &=& F_k^2 + F_{k-1} F_k + F_{k-1}^2 + F_{k-2} F_{k+1}\\\\ &=& (F_k^2 + 2 F_{k-1} F_k + F_{k-1}^2) -F_{k-1} F_k + F_{k-2} F_{k+1}\\\\ &=& (F_k + F_{k-1})^2 -F_{k-1} F_k + F_{k-2} F_{k+1}\\\\ &=& F_{k+1}^2 -F_{k-1} F_k + F_{k-2} F_{k+1}\\\\ &=& F_{k+1}^2 - F_{k-1} (F_{k-2} + F_{k-1}) + F_{k-2} F_{k+1}\\\\ &=& F_{k+1}^2 + F_{k-2} (F_{k+1} - F_{k-1}) - F_{k-1}^2\\\\ &=& F_{k+1}^2 + F_{k-2} F_k - F_{k-1}^2\\\\ &=& F_{k+1}^2 + F_{k-1}^2 + (-1)^k - F_{k-1}^2\\\\ &=& F_{k+1}^2 + (-1)^k\\\\ &=& F_{k+1}^2 + (-1)^{k+2} \end{array}$$Hence, by the principle of mathematical induction, the following holds for all integers $n \ge 1$: $$F_{n-1} \cdot F_{n+1} = F_n^2 + (-1)^{n+1}$$ QED.
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?
To see why this works, consider the terms of the expansion of
$$(x+y)^n = \underbrace{(x+y)(x+y)(x+y) \cdots (x+y)}_{n \textrm{ factors}}$$Each term is formed by choosing either an $x$ or a $y$ from the first factor, and then choosing either an $x$ or a $y$ from the second factor, and then choosing an $x$ or a $y$ from the third factor, etc... up to finally choosing an $x$ or a $y$ from the $n^{th}$ factor, and then multiplying all of these together.
As such, each of these terms will consist of some number of $x$'s multiplied by some number of $y$'s, where the total number of $x$'s and $y$'s is $n$. For example, choosing $y$ from the first two factors, and $x$ from the rest will produce the term $x^{n-2}y^2$. Alternatively, choosing $x$ from the first $7$ factors and $y$ from the rest results in the term $x^7 y^{n-7}$.
Let's consider a specific example. Consider the terms we see from expanding the following expression (assuming we don't collect any "like terms" along the way):
$$\begin{array}{rcl} (x+y)^4 &=& (x+y)(x+y)(x^2 + xy + xy + y^2)\\\\ &=&(x+y)(x^3 + x^2y + x^2y + xy^2 + x^2y + xy^2 + y^3)\\\\ &=&x^4 + x^3y + x^3y + x^2y^2 +x^3y+x^2y^2 + xy^3\\ & &+ x^3y + x^2 y^2 + x^2 y^2 + x y^3 + x y^3 + y^4 \end{array}$$Do you see how every term above takes the form $x^a y^b$ with $a+b=4$?
Now, when we finally "collect like terms", the resulting coefficient on $x^ay^b$ will be the number of times it appears in the expansion. As such, to figure out the coefficient on $x^ay^b$, we just need to figure out how many ways we can form a term that looks like $x^ay^b$.
Consider the terms $xy^3$ above. Note these terms were formed by letting three of the four $(x+y)$ factors contribute a $y$ to the product, with the remaining factor contributing an $x$. As such, the number of these terms will be given by the number of ways we can take $4$ factors and choose $3$ of them to contribute a $y$. In the parlance of combinations, this is given by ${}_4C_3$.
Likewise, the terms $x^2y^2$ were formed by letting $2$ of the $4$ factors contribute a $y$ to the product, with the remaining factors contributing a $x$. Consequently, the number of such terms will be equal to the number of ways we can can take $4$ factors and choose $2$ of them to contribute a $y$. Again, in terms of combinations, this is given by ${}_4C_2$.
In general, we can form terms of the form $x^{n-k}y^k$ by taking $n$ of our factors and choosing $k$ of them to contribute a $y$, which is given in the language of combinations by ${}_nC_k$.
Given that the non-collected terms of the expansion of $(x+y)^n$ can have as few as zero $y$'s or at most $n$ of them (with every integer possibility between), our possible terms are
$$x^n, \quad x^{n-1} y, \quad x^{n-2} y^2, \quad \ldots, \quad x y^{n-1}, \quad y^n$$Finally, noting that in the expansion of $(x+y)^n$, each $x^{n-k}y^k$ occurs ${}_nC_k$ times, we have:
$$(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$$Explain why the technique described for constructing Pascal's triangle yields the same numbers.
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.
As another way to construct Pascal's triangle -- 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 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)!}$$ How do we know the two techniques described for constructing Pascal's triangle yield the same numbers?
Consider the numbers seen in the triangle constructed by looking at the coefficients seen in the expansion of $(x+y)^n$. These are given by the binomial theorem, and all take the form ${}_nC_k$ for some appropriate non-negative integers $n$ and $k$.
Suppose we look at one such number, ${}_nC_k$. This number lies on the $n^{th}$ row. If it lies on an end of this row, then either $k=0$ or $k=n$. Note ${}_nC_0 = {}_nC_n = 1$. This explains the ones seen on the left and right sides of Pascal's triangle.
Now suppose ${}_nC_k$ is not on the end of a row. Then ${}_nC_{k+1}$ would be the number to its right. Likewise, ${}_{n+1}C_{k+1}$ would be the number on the next row, directly below ${}_nC_k$ and ${}_nC_{k+1}$.
As such, we seek to argue that ${}_nC_k + {}_nC_{k+1} = {}_{n+1}C_{k+1}$, as this will establish that the "adding-the-two-above" technique for constructing Pascal's triangle yields the same numbers as the triangle constructed from finding coefficients of $(x+y)^n$ expanded.
We proceed directly...
$$\begin{array}{rcl} {}_nC_k + {}_nC_{k+1} &=& \frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-k-1)!}\\\\\\ &=& \frac{n!}{k!(n-k)!} \cdot \frac{(k+1)}{(k+1)} + \frac{n!}{(k+1)!(n-k-1)!} \cdot \frac{(n-k)}{(n-k)}\\\\\\ &=& \frac{k \cdot n! + n! + n \cdot n! - k \cdot n!}{(k+1)! (n-k)!}\\\\\\ &=& \frac{(n+1) n!}{(k+1)!(n-k)!} \quad = \quad {}_{n+1}C_{k+1} \end{array}$$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?
Suppose we let $f(n)$ denote the number of balls in a pyramid of $n$ layers. Looking at a few small cases, we find:
$$\begin{array}{rcl} f(1) &=& 1\\ f(2) &=& 4\\ f(3) &=& 10\\ f(4) &=& 20\\ f(5) &=& 35\\ f(6) &=& 56 \end{array}$$We might guess $f(n)$ is cubic, and thus of the form $f(n) = an^3 + bn^2 + cn + d$. Under this assumption, we can use the above values to set up a system of equations to solve for $a$, $b$, $c$, and $d$:
$$\begin{array}{rcl} 1 &=& a + b + c + d\\ 4 &=& 8a + 4b + 2c + d\\ 10 &=& 27a + 9b + 3c + d\\ 20 &=& 64a + 16b + 4c + d \end{array}$$Solving, we find $a=1/6, \quad b=1/2, \quad c=1/3, \quad \textrm{ and } d=0$. This suggests that
$$\begin{array}{rcl} f(n) &=& \frac{n^3}{6} + \frac{n^2}{2} + \frac{n}{3}\\\\ &=& \frac{n^3 + 3n^2 + 2n}{6} \end{array}$$Of course, this is still just a guess at this point. We might check $f(5)$ and $f(6)$ to see if we are on the right track...
$$\begin{array}{rcl} f(5) = 35 &\textrm{ and }& \frac{5^3 + 3 \cdot 5^2 + 2 \cdot 5}{6} = \frac{125 + 75 + 10}{6} = \frac{210}{6} = 35\\\\ f(6) = 56 &\textrm{ and }& \frac{6^3 + 3 \cdot 6^2 + 2 \cdot 6}{6} = 6^2 + 3 \cdot 6 + 2 = 36 + 18 + 2 = 56 \end{array}$$Since these check out, we are much more confident that this is the formula we seek, but it remains to prove it...
We proceed by induction...
The table above establishes the basis step, so all that remains is the inductive step.
We need to show that if $f(k) = (k^3 + 3k^2 + 2k) / 6$ balls, then
$$f(k+1) = \frac{(k+1)^3 + 3(k+1)^2 +2(k+1)}{6}$$To show this, first note that a pyramid of $k+1$ layers (with $f(k+1)$ balls) can be split into two pieces -- one consisting of the top $k$ layers, and the other consisting of the bottom layer alone. The first piece, by the inductive hypothesis, contains $f(k) = (k^3 + 3k^2 + 2k) / 6$ balls. The second piece (i.e., the bottom layer) is a triangular arrangement with $1 + 2 + 3 + \cdots + (k+1)$ balls.
Further, we know that
$$1 + 2 + 3 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}$$Thus,
$$\begin{array}{rcl} f(k+1) &=& f(k) + \left[ 1+2+3+\cdots+(k+1) \right]\\\\ &=& \frac{k^3 + 3k^2 + 2k}{6} + \frac{(k+1)(k+2)}{2}\\\\ &=& \frac{k^3+3k^2+2k+3k^2+9k+6}{6}\\\\ &=& \frac{(k^3+3k^2+3k+1)+(3k^2+6k+3)+(2k+2)}{6}\\\\ &=& \frac{(k^3+3k^2+3k+1)+3(k^2+2k+1)+2(k+1)}{6}\\\\ &=& \frac{(k+1)^3 + 3(k+1)^2 + 2(k+1)}{6} \end{array}$$This completes the inductive step, so by the principle of mathematical induction, a pyramid of $n$ layers has $f(n)$ balls where
$$f(n) = \frac{n^3 + 3n^2 + 2n}{6}$$ QED.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.
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$.)
Suppose we denote the number of ways to put $n$ cents in a machine if we use identical nickles, dimes, and quarters by $f(n)$.
The trick here is to "think recursively" and tell yourself that you already know that when $k \lt n$, you can put $k$ cents in the machine in $f(k)$ ways.
As you start dropping change in the machine, you might start by putting in either a nickel, a dime, or a quarter. Let us suppose you put in a nickel. Now you have to ask yourself how many ways can you put in the remaining $n-5$ cents. But $n-5 \lt n$, so this can be done in $f(n-5)$ ways.
If instead, you had put in a dime first, then you have to ask yourself how many ways can you put in the remaining $n-10$ cents. Here again, $n-10 \lt n$, so this can be done in $f(n-10)$ ways.
Lastly, if you first dropped a quarter in the machine, you similarly have $f(n-25)$ ways to put in the remaining change.
Taking these cases together, we arrive at our recursive relationship:
$$f(n) = f(n-5) + f(n-10) + f(n-25)$$All that remains is to identify what happens in the first cases. Note that $f(0) = 1$ and $f(5) = 1$ by inspection. Further, $f(n) = 0$ if $n \lt 0$, as we would need "negative coins" otherwise.
This completes our recursive definition for $f(n)$.
Suppose $F_n$ is the $n^{th}$ Fibonacci number. 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?
| $n$ | $F_n$ | $F_{n+1} / F_n$ |
| 0 | 1 | |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 3 | 1.5 |
| 4 | 5 | 1.666667 |
| 5 | 8 | 1.6 |
| 6 | 13 | 1.625 |
| 7 | 21 | 1.615385 |
| 8 | 34 | 1.619048 |
| 9 | 55 | 1.617647 |
| 10 | 89 | 1.618182 |
| 11 | 144 | 1.617978 |
| 12 | 233 | 1.618056 |
| 13 | 377 | 1.618026 |
| 14 | 610 | 1.618037 |
| 15 | 987 | 1.618033 |
| 16 | 1597 | 1.618034 |
| 17 | 2584 | 1.618034 |
| 18 | 4181 | 1.618034 |
| 19 | 6765 | 1.618034 |
| 20 | 10946 | 1.618034 |
Calculating the first 20 values of $F_{n+1}/F_{n}$ is straight-forward. The results are shown in the table on the left.
You can clearly see that the ratio $F_{n+1} / F_n$ appears to be very close to a constant for large values of $n$. More specifically, it appears that we are multiplying $F_n$ by roughly $1.618034$ each time to find $F_{n+1}$.
This suggests that we might be able to approximate $F_n$ with something of the following form:
$$F_n = C \cdot 1.618034^n$$where $C$ is some constant.
Assuming the above is a good approximation and solving for $C$, we find $C \approx F_n / 1.618034^n$ when $n$ is large enough. For $n=20$, this yields $C \approx 0.723607$.
So it appears that we can approximate $F_n$ with the following formula:
$$F_n = 0.723607\cdot 1.618034^n$$Indeed, this formula does a great job approximating $F_n$, predicting its value exactly (provided one rounds to the nearest integer) all the way up to $n=29$. Further, had we better approximated the apparent constant $1.618034...$, the resulting formula would have worked all that much longer.
This begs the question, however -- what is the exact value of the constant $1.618034...$ that we seek, and is there anything significant about it? Hmmm....
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$.
Find the value of $\varphi = a/b$, dubbed the golden ratio.
We know that
$$\frac{a+b}{a} = \frac{a}{b}$$If we wish to solve for $a/b$, it would be helpful if this was the only unknown in the equation. That is to say, if $x=a/b$, can we rewrite our equation so that it is in terms of only $x$?
We can turn the $a$ in the denominator into an $a/b$ by dividing it by $b$. So that we don't alter the value of the expression on the left, let us do this to the numerator as well, yielding
$$\frac{a/b + 1}{a/b} = \frac{a}{b}$$Now, we can replace each $a/b$ with $x$ as suggested above, and then simply solve for $x$
$$\frac{x+1}{x} = x$$Clearing the fractions by multiplying by $x$, we have
$$x+1 = x^2$$This of course is quadratic, so its solution is routine.
$$x^2-x-1=0$$which yields
$$x = \frac{1 \pm \sqrt{5}}{2}$$Knowing that $x = a/b$ is a ratio of side lengths, it must be true that $x>0$, so we can eliminate the negative solution found. Thus, the remaining solution must be the value of the golden ratio, $\varphi$, that we seek:
$$\varphi = \frac{1 +\sqrt{5}}{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)
Suppose $\varphi$ denotes the golden ratio and $\phi$ denotes its negative reciprocal. Find the first few powers of each. What can you say about their differences, $\varphi^n - \phi^n$? Make a conjecture and prove it with induction.
Recall, the golden ratio is given by
$$\varphi = \frac{1+\sqrt{5}}{2}$$First, we need to find the value of $\phi$, the negative reciprocal of the golden ratio, $\phi$,
$$\begin{array}{rcl} \phi &=& -\frac{2}{1+\sqrt{5}}\\\\ &=& -\frac{2}{1+\sqrt{5}} \cdot \frac{1-\sqrt{5}}{1-\sqrt{5}}\\\\ &=& \frac{-2(1-\sqrt{5})}{-4}\\\\ &=& \frac{1-\sqrt{5}}{2} \end{array}$$Now if we expand and simplify $\varphi^n - \phi^n$ for the first few positive integers $n$, we find:
$$\begin{array}{cccc} \left( \frac{1 + \sqrt{5}}{2} \right)^1 - \left( \frac{1 - \sqrt{5}}{2} \right)^1 & = & \sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^2 - \left( \frac{1 - \sqrt{5}}{2} \right)^2 & = & \sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^3 - \left( \frac{1 - \sqrt{5}}{2} \right)^3 & = & 2\sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^4 - \left( \frac{1 - \sqrt{5}}{2} \right)^4 & = & 3\sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^5 - \left( \frac{1 - \sqrt{5}}{2} \right)^5 & = & 5\sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^6 - \left( \frac{1 - \sqrt{5}}{2} \right)^6 & = & 8\sqrt{5} \\\\ \left( \frac{1 + \sqrt{5}}{2} \right)^7 - \left( \frac{1 - \sqrt{5}}{2} \right)^7 & = & 13\sqrt{5} \end{array}$$We conjecture that $\varphi^n -\phi^n = F_n \sqrt{5}$ where $F_n$ is the $n^{th}$ term of the Fibonacci sequence. Recall the terms of the Fibonacci sequence are defined by the recursive relationship $F_n = F_{n-1} + F_{n-2}$ along with $F_0=F_1=1$.)
We argue by strong induction...
The basis step is already well established by the calculations in the list above.
Proceeding with the inductive step, we need to show that if $\varphi^n -\phi^n = F_n \sqrt{5}$ for every $n \le k$, then $\varphi^{k+1} -\phi^{k+1} = F_{k+1} \sqrt{5}$.
Working from the right side to the left, we have
$$\begin{array}{rcl} F_{k+1} \sqrt{5} &=& \sqrt{5} (F_k + F_{k-1})\\\\ &=& \sqrt{5} F_k + \sqrt{5} F_{k-1}\\\\ &=& \sqrt{5} \left( \frac{\varphi^k - \phi^k}{\sqrt{5}} \right) + \sqrt{5} \left( \frac{\varphi^{k-1} - \phi^{k-1}}{\sqrt{5}} \right) \quad \quad \textrm{...by the inductive hypothesis}\\\\ &=& \varphi^k - \phi^k + \varphi^{k-1} - \phi^{k-1}\\\\ &=& (\varphi^k + \varphi^{k-1}) - (\phi^k + \phi^{k-1})\\\\ &=& \varphi^{k-1} (\varphi + 1) - \phi^{k-1} (\phi + 1)\\\\ &=& \varphi^{k-1} \varphi^2 - \phi^{k-1} \phi^2 \quad \quad \textrm{...see note below}\\\\ &=& \varphi^{k+1} - \varphi^{k+1} \end{array}$$Note: the last two steps may not seem obvious at first blush, but remember we know where we are headed. We know we need to link up the left side and right side below: $$\varphi^{k-1} (\varphi + 1) - \phi^{k-1} (\phi + 1) = \cdots = \varphi^{k+1} - \varphi^{k+1}$$
So it sure would be nice if $\varphi + 1 = \varphi^2$ and $\phi + 1 = \phi^2$. Since we know the exact values of $\varphi$ and $\phi$, we can check to see if this is the case by simple evaluation -- and it is:
$$\left( \frac{1 \pm \sqrt{5}}{2} \right) + 1 = \frac{3 \pm \sqrt{5}}{2}$$(Alternatively, if you recall that $\varphi$ and $\phi$ are the roots of the quadratic equation $x^2 -x - 1 = 0$, then isolating the $x^2$ on one side reveals the desired relationship immediately.)
This completes the induction step, so by the second principle of mathematical induction (i.e., strong induction), the following holds for all positive integers $n$: $$\varphi^n -\phi^n = F_n \sqrt{5}$$ QED.
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.)
🔎 Into how many regions is the plane divided by $n$ lines where no two of the lines are parallel, and no three lines meet at a single point?
🔎 Lockers in a row are numbered 1, 2, 3, ..., 1000. At first, all the lockers are closed. A person walks by, and opens every other locker, starting with locker #2. Another person walks by and changes the 'state' of every third locker starting with locker #3. Changing the 'state' means closing open lockers and opening closed lockers. Then another person changes the state of every fourth locker starting with locker #4. This process continues until no more lockers can be altered. Which lockers will be closed?
🔎 Let $x = 1^1 + 2^2 + 3^3 + 4^4 + \cdots + 100^{100}$. Find the unit's digit of $x$.
🔎 Let $N$ denote the natural numbers $\{1, 2, 3, 4, \ldots\}$. Consider a function $f : N \rightarrow N$ which satisfies $f(1) = 1$, $f(2n) = f(n)$, and $f(2n+1) = f(2n) + 1$ for all $n \in N$. Find a simple algorithm for computing $f(n)$. Your algorithm should be a single sentence long, at most.
🔎 Consider $f_b f_c + f_{b+1}f_{c+1}$ for a variety of natural numbers $b$ and $c$, where $f_n$ is the $n^{th}$ Fibonacci number. (Recall the $n^{th}$ Fibonacci number is defined by $f_1 = 1$, $f_2 = 1$ and $f_n = f_{n-1} + f_{n-2}$ for all $n \gt 2$.) You should notice that each such sum seems to also always be a Fibonacci number. Conjecture which Fibonacci number the sum should be in terms of $b$ and $c$ and then prove your conjecture.
🔎 Make a conjecture about the value $f_{b+1} f_{b-1} - f_{b}^2$ after considering a variety of natural numbers $b$. As always, $f_n$ represents the $n^{th}$ Fibonacci number defined by $f_1 = 1$, $f_2 = 1$ and $f_n = f_{n-1} + f_{n-2}$ for all $n \gt 2$. Then prove your conjecture.
🔎✭ Suppose that $n$ quarters are stacked so that they are all "heads up". The top coin is removed, flipped over, and then replaced on the top of the stack. Then, the top two coins are removed, flipped over (as a group), and then replaced on the top of the stack. Then, this is done to the top three coins, and then the top four coins, etc..., until finally, the entire stack of $n$ coins is flipped over. Then, this process is repeated, starting again with flipping just the top coin. How many flips does it take to return the stack to "all heads up"?