Fibonacci Series: Introduction

Based on popular requests, I'm going to start a new series of posts called the Fibonacci Series (HA!)

It will explore a number of combinatorial interpretations of the Fibonacci series, and the elegance with which we could prove some Fibonacci-related theorems, using purely combinatorial arguments and minimal algebra.

Definition

A sequence $F_n$ is defined by $F_0 = 1, F_1 = 1$ and $F_{n+2} = F_{n+1} + F_n$. This sequence is called the Fibonacci sequence. The first few terms of the sequence is (starting with $F_0$): 1,1,2,3,5,8,13,21,...

Suppose there is a stair with $n$ steps, and one can climb it using "steps" or using "hops" where each step ascends the person by 1 step of stair, and each hop ascends the person by 2 steps.

For a stair with 2 steps, there are 2 ways one can climb it. By using 2 steps, or a hop. For a stair with 3 steps, there are 3 ways: step-hop, hop-step, or step-step-step. For 4 steps, there are 5 ways: 4 steps, step-step-hop, step-hop-step, hop-step-step, hop-hop.

Theorem: In general, for a stair with $n$ steps, there are exactly $F_n$ ways to climb it.

Proof:
Proof by induction.

The first action that one can take could be a step or a hop. If the first action is a step, then the climber must ascend the remaining $n-1$ steps with combinations of steps and hops. There are $F_{n-1}$ such ways.

If the first action is a hop, then the climber must ascend the remaining $n-2$ steps, and there are $F_{n-2}$ ways to do so.

These two cases are mutually exclusive, so in total there are $F_{n-1} + F_{n-2}$ ways to climb. This is exactly the recursive equation for the Fibonacci series, and since the first few terms agree, we conclude that in general the number of ways to climb an $n$-step stair is $F_n$.

Exercise:

There are many more possible combinatorial interpretations of the Fibonacci sequence. For the rest of the series, we are going to use the stair-climbing interpretation, but the following interpretations are just as useful.

1. Prove that $F_{n+1}$ is the number of binary numbers with $n$ digit such that there are no two consecutive zeroes.

2. Prove that $F_{n+1}$ is the number of subset from the set $\{ 1, 2, \dots, n \}$ without two consecutive numbers.

3. Prove that $F_{n-2}$ is the number of ways to tile a $1 \times n$ board with tiles of length 2 or longer.

4. Prove that $F_{n-1}$ is the number of ways to tile a $1 \times n$ board with tiles that have odd length.

5. Prove that $F_n$ is the number of permutation $(a_1, \dots, a_n)$ of $\{ 1, \dots, n \}$ such that for each $i$, $|a_i - i| \leq 1$.

6. Prove that $F_{2n+1}$ is the number of ternary numbers with $n$ digits where a 0 is never followed by a 2.

Are you smarter than a 6th grader?

This problem was proposed to a math olympiad for 6th graders. The solution doesn't require any algebra nor any more advanced tools, other than simply logic.


Problem


Each apple costs 1 dollar and each orange costs 1.01 dollar. Johnny has 101 dollars. How many ways are there for him to buy fruits, including possibly not buying anything? Sarah has 99 dollars. How many ways are there for her to buy fruits, including possibly not buying anything?

Solution

First we make an observation that 100 and 101 are relatively prime. So suppose Johnny buys X apples and Y oranges and spends exactly Z amount of money. If he wants to spend EXACTLY Z amount of money with a different combination of fruits, he would have to decrease X by 101 and increase Y by 100, or increase X by 101 and decrease Y by 100.

For Johnny,

Consider case 1: If Johnny spends exactly 101 dollars. Clearly he can buy 101 apples or 100 oranges, but these are the only two cases.

Case 2: If Johnny spends less than 101 dollars. Now, pretend that the store only has 101 apples and 100 oranges (since Johnny can’t buy more apples or more oranges than these).

Consider all the combinations of apples and oranges that Johnny can buy, and consider what’s left at the store. The total amount of goods in the store are 1 dollar x 101 + 1.01 dollar x 100 = 202 dollars. So if Johnny spends less than 101 dollars, the total amount goods left in the store is greater than 101 dollars. We can’t reverse this situation, that is, Johnny can never spend more than 101 dollars so that the total amount left in the store is less than 101 dollars.

This means, in all the possible combinations of x apples (x is from 0 to 101 inclusive) and y oranges (from 0 to 100 inclusive), for each combination that Johnny can buy, there is precisely one combination that Johnny couldn’t buy. The combinations that Johnny couldn’t buy represent the amount that would be left in the store if Johnny had bought the “complement” combination instead.

The total number of combinations is 102 x 101 = 10302, (because we go from 0 apples to 101 inclusive, 0 oranges to 100 inclusive) but we have to subtract two combinations from case 1, so we have 10 300, split evenly between what Johnny could buy and couldn’t buy. So Johnny could buy 5150 combinations.

Together from Case 1 and Case 2, Johnny could buy fruits in 5152 ways.

For Sarah,

Case 1: She spends exactly 99 dollars. She can buy 99 apples. She couldn’t buy any oranges because if she wants to buy any oranges she’d have to increase it in increments of 100 and decrease the apples in increments of 101, again because 101 and 100 are relatively prime.

Now, consider the story of Johnny. Out of 5150 ways he could buy fruits, categorize them according to his spending:
Category 1: He spends 0 to 98.99
Category 2: He spends 99 exactly
Category 3: He spends 99.01 to 100.99
Category 4: He spends 101

Suppose he buys a certain number of apples and oranges. In order to keep the spending amount intact and changes the number of apples or oranges, as we’ve noted above, he would have to change the number of apples and oranges in increments of 101 and 100 respectively. The total amount of goods being changes (from apples to oranges or vice versa) is already 101 dollars. This is why in category 4 he has two ways of buying good. But this means, in category 1, 2, and 3, for each spending amount, there’s at most one (possibly zero) way to buy fruits with that spending amount.

Now, we show that 98.99 dollars spending amount is unattainable. Johnny could achieve that amount by buying 100 apples and –1 oranges, or –1 apples and 99 oranges. Neither one are reasonable.

Next, for each amount in category 1, we pair them up. We pair up X with 98.99 – X. For example, 0 and 98.99 is paired up. 0.01 and 98.98 is paired up, etc.

We claim that within each pair, at most one value is attainable, possibly zero. If both values are attainable, say if Johnny could buy A apples and B oranges with X dollars and C apples and D oranges with 98.99 – X dollars, then he could buy (A+C) apples and (B+D) oranges with 98.99 dollars, a contradiction since we’ve shown that 98.99 is unattainable. So since there are 9900 values, and thus 4950 pairs of values, so there are at most 4950 ways to buy fruits in category 1.

But then there is 1 way in category 2, and total of 5150 ways in category 1,2,3 altogether. So there are at least (5150 – 1 – 4950) = 199 ways to buy in category 3. But notice that there are exactly 199 values (amounts) in category 3, each of which can correspond to at most one way to buy fruits. Thus we must have that each value in category 3 is attainable by exactly one way of buying, and each pair of values in category 1 is attainable by exactly one way of buying.

So in total, when Sarah spends her money, she can spend it from category 1 or 2, and there are 4950 + 1 = 4951 ways of buying.

General Recursion

Given a recursive formula with $a_{n+1} = 2a_n -1$ and $a_1 = a$, find a general formula for $a_n$.

a,b,c fraction integer

Given positive integers $a,b,c$ such that
$$\frac{a}{b} + \frac{b}{c} + \frac{c}{a}$$
is also an integer, show that
$$\frac{a^2b^2}{c},\frac{b^2c^2}{a}, \frac{c^2a^2}{b}$$
are all cubic numbers.

Sequence modulo 2011

A sequence of integers $a_1, \dots, a_{2010}$ satisfy the following properties:

$a_1 - 1$ is divisible by 2011
$a_k a_{k-1} - k$ is divisible by 2011 for $k = 2, 3, \dots, 2010$

Show that $a_{2010} + 1$ is divisible by 2011.

Solution

First we prove the following assertion:

For $k$ odd, then $a_k.2.4.6. \cdots.(k-1) - 1.3.5.\cdots.k$ is divisible by 2011.
For $k$ even, then $a_k.1.3.5. \cdots .(k-1) - 2.4.6.\cdots.k$ is divisible by 2011.

Proof by induction. It can easily be seen for $k=1$ it's true. For $k=2$, we have $2011 | a_2a_1 - 2 = a_2(a_1-1) + (a_2-2)$ So $2011 | a_2 - 2$

Suppose it's true for $k-1$ odd, then for $k$ even:
$2011 | a_k a_{k-1} - k$ which means
$$2011 | 2.4.\cdots.(k-2) (a_k a_{k-1} - k) = 2.4.\cdots.(k-2)a_k a_{k-1} - 2.4.\cdots.(k-2).k$$
$$2011 | a_k (2.\cdots.(k-2)a_{k-1} - 1.3.\cdots.(k-1)) + (a_k.1.3.\cdots.(k-1) - 2.\cdots.(k-2).k)$$
And since 2011 divides the first term by induction hypothesis, then it also divides the second term, which completes the induction step. The proof for $k-1$ even and $k$ odd is similar.

Now, that means for $k=2010$, let $X = a_{2010}$ we have:
$$2011 | X.1.3. \cdots .2009 - 2.4.\cdots.2010$$

We now prove the following assertion for $i = 1,2,\dots,1005$
$$2011 | X.1.3. \cdots. (2011-2i) + (-1)^i (2i) (2i+2)\cdots.2010$$

For $i = 1$ it is true by definition. Now suppose it's true for $i-1$, then for $i > 1$:
$$2011 | X.1.3. \cdots. (2011 - 2i).(2011-2i+2) +(-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a(2011+b) + c$ then $2011 | ab+c$
$$2011 | X.1.3. \cdots. (2011 - 2i).(-2i+2) + (-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a$ then $2011 | -a$.
$$2011 | X.1.3. \cdots. (2011 - 2i).(2i-2) + (-1)^{i} (2i-2) (2i)\cdots.2010$$
$$2011 | 2(i-1)(X.1.3. \cdots. (2011 - 2i).+ (-1)^{i} (2i)\cdots.2010)$$
if $2011 | 2(i-1)a$ then $2011 | a$ since 2011 is prime and $i > 1$.

So the assertion holds for $i = 1,\dots, 1005$. Particularly, for $i = 1005$ we have:
$$2011 | X - 2010$$
$$2011 | X + 1 - 2011$$
$$2011 | X + 1$$

Colored chessboard

An $n \times n$ chessboard is put on the table such that its sides are facing the North, East, South, and West. Each cell is then colored either with red, green, blue, or yellow paint such that:
1. The North-most cells are colored only with red or green
2. The East-most cells are colored only with green or blue
3. The South-most cells are colored only with blue or yellow
4. The West-most cells are colored only with yellow or red

Prove that there is a point that serves as a vertex to at least three squares of different colors.

Solution


For each cell that has color red, green, blue, and yellow, give it a rank of 1,2,3, and 4 respectively.

Then for each "side" (a segment of line between two cells), mark it if:
1. It delineates two cells. That is, sides that coincides with the sides of the large chess board cannot be marked.
2. Those two cells have a rank differing by exactly 1.

Now, for each vertex, give it a score as follows:
1. The score of each vertex is the number of marked sides that border it. Thus, each cell might have a score of 0, 1, 2, 3, or 4.
2. Vertices that lie on the sides of the large chess board also get their own score. These vertices cannot have a score of 4 of course, but give it a score regardless. Call these vertices the "border vertices" as opposed to "inner vertices"

We assert the following: if an inner vertex has an odd score, then it serves as a vertex to at least three squares of different colors. In other words, an inner vertex with an odd score is the vertex whose existence we seek to prove.

Indeed, it is impossible to form an inner vertex with a score of 1 or 3 with merely one or two colors. For example, if the four squares surrounding the vertex has colors R,G,G,R, then the squares would have ranks of 1,2,2,1, and there are two marked sides. The other combinations are left to the reader as an exercise.

Now, let $A$ be the sum of scores among the inner vertices, and $B$ be the total number of scores among the border vertices. $A+B$ must be even since each marked side contributes two points of score to that total.

We will show that $B$ is odd. The Northwest (NW) corner must be colored red, and the NE corner must be colored green, and the North side must be colored only red or green. Thus, the North side changes color an odd number of times, and each change of color is between a red and a green, producing an odd number of marked sides in the process. These marked sides contribute 1 point each to $B$.

The same argument can be made to the East side and the South side, but not the West side. In fact, none of the color changes on the West side contribute to $B$ at all since they're between a cell of rank 1 and rank 4. So in total, $B$ is a sum of three odd numbers, which means $B$ is odd.

Since $A+B$ is even, then $A$ is odd. That means there must be at least one inner vertex that has an odd score, showing the existence of our desired vertex.

liars and honest villagers

In a village, there are $n$ people who each has an ID number from 1 to $n$. Each person is either completely honest or a total liar. One day, a detective came to visit and interviewed them. This is what they told him:

If a person had an ID number $x$ where $x$ is even, he said:
"The person whose ID number is $x/2$ is honest"

If a person had an ID number $x$ where $x$ is odd and greater than one, he said:
"The person whose ID number is $(x-1)/2$ is a liar"

Person with ID number of 1 did not say anything.

If $L$ is the number of liars and $H$ is the number of honest villagers, find all possible values of $L-H$