Combinatorics: How to prove it?

64 Views Asked by At

Assume there are $k$ infinite arithmetic sequences called (for 0<=i<=k) $S_i = (a_i, a_i+d_i, a_i+2d_i, ...)$ with a difference of $d_i$ and first value of $a_i$. If each natural number belongs to exactly one of the sequences $S_i$ prove that: $$\frac{1}{1-x} = \sum_{i = 0}^{k}\frac{x^{a_i}}{1-x^{d_i}}$$

1

There are 1 best solutions below

1
On BEST ANSWER

$$\sum_{i=0}^{k} \frac{x^{a_i}}{1-x^{d_i}} = \sum_{i=0}^{k} x^{a_i}(1+x^{d_i}+x^{2d_i}+\dots)=\sum_{i=0}^{k}x^{a_i} + x^{a_i+d_i}+x^{a_i+2d_i}+\dots$$

Now since each natural number belongs to exactly one of the sequences, this is simply equal to $$1+x+x^2+x^3+\dots = \frac{1}{1-x}.$$