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.]

2 comments:

  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.

    ReplyDelete