Tuesday, February 13, 2007

Lots of Fn. Topic: Algebra/S&S. Level: AIME.

Problem: Let $F_n$ be the Fibonnaci sequence that begins with $F_1 = 1$, $F_2 = 1$, etc. Show that

$F_{2n} = F_{n+1}^2-F_{n-1}^2$.

Solution: We will use induction (as expected). First, rewrite the equality as

$F_{2n} = F_{n+1}^2-(F_{n+1}-F_n)^2 = F_n(2F_{n+1}-F_n)$.

The base case is easy, since we have $F_4 = 3 = 2^2-1^2 = F_3^2-F_1^2$. Now we will show that it is true for $n = k+1$ assuming it is true for $n \le k$. We have

$F_{2k+2} = F_{2k+1}+F_{2k} = 3F_{2k}-F_{2k-2}$.

Now we apply the inductive hypothesis to get

$F_{2k+2} = 3F_k(2F_{k+1}-F_k)-F_{k-1}(2F_k-F_{k-1})$,

which we can simplify with the substitution $F_{k-1} = F_{k+1}-F_k$ to get

$F_{2k+2} = 3F_k(2F_{k+1}-F_k)-(F_{k+1}-F_k)(3F_k-F_{k+1}) = 2F_kF_{k+1}+F_{k+1}^2$

and finally from $F_k = F_{k+2}-F_{k+1}$ we get

$F_{2k+2} = F_{k+1}(2F_{k+2}-F_k)$

as desired. QED.

--------------------

Comment: Not a particularly insightful problem, but admittedly a pretty neat identity. Standard substitution/induction method, which you should all be familiar with right now since I use it all the time here. Maybe there's some cool combinatorics argument that I can't see...

--------------------

Practice Problem: Show $F_{2n} = F_n^2+F_{n-1}^2$ through a combinatorics argument, where $F_0 = 1$, $F_1 = 1$, etc. is the Fibonnaci sequence.

[Hint: $F_n$ is the number of ways to tile a $2 \times n$ board with $1 \times 2$ tiles.]

1. Ooh, that's a really nice practice problem. Okay, so consider tiling a 2x2n board, and consider the middle two squares.

Case: A 1x2 tile is in the middle two squares. Then the top 2x(n-1) half can be tiled F_{n-1} ways and so can the bottom half, so F_{n-1}^2 tilings are possible.

Case: A 1x2 tile is not in the middle two squares. Then the top and bottom halves are just 2xn boards, so there are F_n^2 tilings.

2. Yup, very cool.