A few interesting problems for you to think about:
- Given a positive integer n, in how many ways can n be written as a sum of powers of two, when each power is allowed to occur at most once? For example, 11 can be written as . But we’re not allowed to write , since occurs twice. The order of the terms in the sums don’t matter, so and don’t count as different sums.
- Now what if we allow at most two copies of each power of two? Both of the examples for 11 shown above would be allowed now. Say denotes the number of different ways to write n as a sum of powers of two with at most two copies of each power allowed. What can you say about the function h?
- What if we allow an unlimited number of each power of two? Now how many ways are there to write n as such a sum?
Post your solutions in the comments (partial solutions are welcome and encouraged), but only if you didn’t know the answer as soon as you read the question. =)