Ordered Sums

Problem | Solution | Printable page |
Stage: 4 Challenge Level: Challenge Level:2 Challenge Level:2

Let a(n) be the number of ways of expressing the integer n as an ordered sum of 1's and 2's. For example, a (4) = 5 because:

4 = 2 + 2
2 + 1 + 1
1 + 2 + 1
1 + 1 + 2
1 + 1 + 1 + 1.

Let b(n) be the number of ways of expressing n as an ordered sum of integers greater than 1.

(i) Calculate a(n) and b(n) for n 8. What do you notice about these sequences?
(ii) Find a relation between a(p) and b(q) .
(iii) Prove your conjectures.
search engine page

Published April 1998.