dimension of space of polynomials

Let $\mathcal P_k^n$ be the space of all polynomials of degree $\leq k$ in $n$ variables. Prove $\dim\mathcal P_k^n = {n+k\choose k}$.

I tried showing this by taking $n\in\mathbb N$ an arbitrary number and using induction for $k$ to show that the formula holds, but couldn't work out the inductive step. How do I work this out?

Introduce a dummy variable $x_0$ and count all monomials of exact degree $k$ in the $n+1$ variables $x_0$, $x_1$, $\ldots$, $x_n$. This is a "stars and bars problem": We have $k$ stars in $n+1$ groups and $n$ bars separating the groups, making a total of $$N={n+k\choose n}$$ such arrangements. This number $N$ is the dimension of your space ${\cal P}_k^{(n)}$.

• Is this dummy variable the number 1 I need for my basis of $\mathcal P_k^n$? Jun 15, 2013 at 18:02
• @dinosaur: I'd rather call it a combinatorial trick. Jun 15, 2013 at 18:25

Let $S=\{\displaystyle \prod_{i=0}^{n} x_i^{\alpha_i}|x_0=1,\alpha_i\ge 0\text{ and }\displaystyle \sum_{i=0}^{n}\alpha_i=k\}$. Then S forms a basis of this subspace.

So it sufficices to show that no. of solutions of $\displaystyle \sum_{i=0}^{n}\alpha_i=k$ with $\alpha_i\ge 0$ is $\binom{n+k}{k}$

• Thanks for this idea, I'm currently trying to work things out following your direction, but I'm confused with your definition of S. Shouldn't it be $S =\{\prod_{i=0}^n x_i^{\alpha_i} | x_0=1, \alpha_i\geq 0 \mathrm{\ and\ }\sum_{i=0}^n \alpha_i = k\}$ as $n\neq k$? Jun 15, 2013 at 17:55
• @dinosaur Yes... you are right ....and thanks for pointing it out. Jun 15, 2013 at 18:35
• okay, so I think I've been able to work this out starting with your idea and using Christians "stars and bars" problem as a guide through the counting of the number of solutions for $\sum_{i=0}^n \alpha_i = k$. Jun 15, 2013 at 18:49
• @dinosaur I had thought of writing down the bars and balls(as it is known to me) procedure,but it occurred to my mind you might know it already so there is no point in writing that out. Jun 15, 2013 at 18:57

Hint: $${n+k\choose k}=\left(\!\!\!{n+1\choose k}\!\!\!\right)$$ where $\left(\!\!{n+1\choose k}\!\!\right)$ denotes the multichoose function.

If we choose $k$ times from the set $\{x_1,x_2,\ldots, x_n,1\}$, with repetition allowed, and multiply the result, we will get a monomial of degree $\le k$.