code Kata 3, How many n-digit binary numbers are there that don't have two adjacent 1 bits?

Today I read a new Kata from Dave's CodeKataCodeKata fifteen: A diversion

The Question:
Think of binary numbers: sequences of 0's and 1's. How many n-digit binary numbers are there that don't have two adjacent 1 bits? For example, for three-digit numbers, five of the possible eight combinations meet the criteria: 000, 001, 010, 011, 100, 101, 110, 111. What is the number for sequences of length 4, 5, 10, n?

Having worked out the pattern, there's a second part to the question: can you prove why that relationship exists?

The answer is in the replied comments, it is a fibonacci series:
f(1) = 2 => 0,1
f(2) = 3 => 00, 01, 10
f(n) = f(n-1) + f(n-2)

Now I will try to explain why it is like this using my own thoughts:
f(3) can be thought of 2 groups, one is begin with 0, and the other is begin with 1
begin with 0 group: 0 + xx, => f(2)
begin with 1 group: since it begins with 1, it must be followed by 0, so it becomes 10 + x , =>f(1)

so f(3) = f(2) + f(1)

same thing with f(n)
begins with 0: 0 + xxx...x ( n-1 digit) => f(n-1)
begins with 1: 10 + xxx..x ( n-2 digit) => f(n-2)

so f(n) = f(n-1) + f(n-2)

Now I will give the solution in Ruby:

def non_adjacent_one_array(n)
if(n == 1)
["0", "1"]
elsif (n== 2)
["00", "01", "10"]
else
array1 = non_adjacent_one_array(n-1).collect { |i| "0"+i}
array2 = non_adjacent_one_array(n-2).collect { |i| "10"+i}
array1+array2
end
end

s=non_adjacent_one_array(5)
puts "n=5, number is #{s.length}\n"
puts s
puts "\n"

1.upto(10) do |i|
s = non_adjacent_one_array(i)
puts "n=#{i} number=#{s.length}\n"
end


And the results are:

n=5, number is 13
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101

n=1 number=2
n=2 number=3
n=3 number=5
n=4 number=8
n=5 number=13
n=6 number=21
n=7 number=34
n=8 number=55
n=9 number=89
n=10 number=144