All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Odd partition (Posted on 2019-05-09) Difficulty: 3 of 5
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.)
Solution 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:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information