 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Odd partition (Posted on 2019-05-09) 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

 No Solution Yet Submitted by Danish Ahmed Khan No Rating Comments: ( Back to comment list | You must be logged in to post comments.) The Fibonacci connection Comment 2 of 2 | 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 Please log in:

 Search: Search body:
Forums (0)