There are 3 ways to write 4 as a sum of odd numbers (assuming order matters and numbers can be repeated in the sum): 3+1, 1+3, and 1+1+1+1.
How many ways are there to write 19 as a sum of odd numbers?
Hint: The above result has something to do with Fibonacci numbers
The sequence builds as the Fibonacci numbers because each term comes from the previous two as follows:
0 ways to write 0: _
1 way to write 1: 1
1 way to write 2: 1+1
To write n,
add 2 to the final number in every way to write n-2
add an extra +1 to the end of every way to write n-1
2 ways to write 3:
3
1+1+1
3 ways to write 4:
1+3
3+1
1+1+1+1
5 ways to write 5:
5
1+1+3
1+3+1
3+1+1
1+1+1+1+1
So you can just look up the 19th Fibonacci number: 4181
(Also the OEIS entry
https://oeis.org/A000045 has this in comments:
F(n) = number of compositions of n into odd parts; e.g., F(6) counts 1+1+1+1+1+1, 1+1+1+3, 1+1+3+1, 1+3+1+1, 1+5, 3+1+1+1, 3+3, 5+1. - Clark Kimberling, Jun 22 2004)
|
|
Posted by Jer
on 2019-05-09 21:38:10 |
The Fibonacci connection
