Generating Function of Integer Partitions

247 Views Asked by At

Let $p_{k}(n)$ be a number of partitions of $n$ that into parts not greater than $k$.

$p_{k}(n)=p_{k-1}(n)+p_{k}(n-k)$

i will prove this partition recurrence bu using Generating Functions of Integer partitions. In fact i have an idea but i am not sure whether it is true or not.we can see that;

$$ P(\leq k)=P(=k)+P(\leq k-1) $$ So we have $$ \begin{aligned} &\frac{1}{(1-q)\left(1-q^{2}\right)\dots\left(1-q^{k}\right)}=\frac{q^{k}}{(1-q)\left(1-q^{2}\right)\dots\left(1-q^{k}\right)}\\ &+\frac{1}{(1-q)\left(1-q^{2}\right)\dots\left(1-q^{k-1}\right)} \end{aligned} $$

Since this equality is provided,this proof is completed.i dont know my opinion is right or not?can anyone help please? Have i any mistake?

We can also think any different solutions? Maybe from bijective proof and ferrers diagrams?i am also open and another solutions.thanks.

1

There are 1 best solutions below

4
On BEST ANSWER

Your argument seems OK but might be more complicated than necessary. You can instead derive the recurrence from first principles by conditioning on whether a partition contains a part of size $k$ or not. If it does, then removing $k$ yields a partition of $n-k$ into parts $\le k$. If it doesn't, then you have a partition of $n$ into parts $\le k-1$.