Analysis and Combinatorics

We often hear about how all mathematics is interconnected, but rarely see clear and simple examples of such connections. In this post I want to show one example in which theorems developed in Calculus are used to solve a range of combinatoric problems.

To begin lets consider the following problem. For any natural number K what is the number of ways it can be written as a sum of powers of two, if we allow each of them to be used only ones? Lets suppose that the number of ways is a(k). It is obvious that a(1)=1, a(2)=1. Lets define a function:

f(x)=a(0)+a(1)x+a(2)x^2+....
a(0)=1

It is easy to see that if a(k) is defined this way then it is also true that:

f(x)=(1+x)(1+x^2)(1+x^4)(1+x^8)......

This is true because if we open the brackets we will get that x^k appears exactly a(k) times. Now lets multiply f(x) by (1-x). It is easy to show that:

(1-x)f(x)=1

You show this by looking on a finite multiplication and then taking limit. However, now we got that:

f(x)=1/(1-x)=1+x+x^2+x^3+x^4+.....

This is true because this is the formula for the sum of the geometric series for any 0<1. style="text-align: center;">F(n)=F(n-1)+F(n-2) , F(0)=0, F(1)=1
f(x)=F(0)+F(1)x+F(2)x^2+....

Lets look on the following multiplications xf(x), x^2f(x). Because of the recursive formula we get:

f(x)(1-x-x^2)=F(0)+(F(1)-F(0))=1

f(x)=1/(1-x-x^2)

The only thing left to do is to calculate the series and we are done. This part is left as an exercise for the bored reader. The important thing is that the same idea works for any different series - this is not something that is true only in a specific case. As such this is indeed an example of how mathematics is interconnected and how calculus that is the study of infinite can be used to solve finite combinatoric problems.