Find the number of natural solutions for $x_1 +x_2 + \cdots + x_k = n$, with $ x_i \notin 3\mathbb{N}$.

Question

Find the number of natural solutions for $$x_1 +x_2 + \cdots + x_k = n,$$ with the constraints $x_i \notin 3\mathbb{N}$ for $i=1,2,\dots,k$.

My Attempt:

the generating function of the equation is: $f(x) =(x+x^2)(1+x^3 +x^6+\cdots +x^{3k} +\cdots)$

Now I know that for $g(x) = 1+x+x^2+\dots +x^k +\cdots = \ \sum_{k=0}^\infty x^k = \frac{1}{1-x}$

does that mean that $f(x) =(x+x^2)(1+x^3 +\cdots +x^{3k} +\cdots)= \sum_{k=0}^\infty (x^{3k})\cdot(x+x^2) = \frac{(x+x^2)}{1-x^{3k}}$

But How do I Continue with my function?

Answer 1

The generating function is $$ \left(\frac{x+x^2}{1-x^3}\right)^k\tag1 $$ since each variable can take values in the exponents of $$ \frac{x+x^2}{1-x^3}=x+x^2+x^4+x^5+x^7+x^8+\dots\tag2 $$ Compute the coefficient of $x^n$ in $(1)$: $$ \begin{align} \left[x^n\right]\left(\frac{x+x^2}{1-x^3}\right)^k &=\left[x^{n-k}\right]\left(\frac{1+x}{1-x^3}\right)^k\\ &=\left[x^{n-k}\right]\sum_{i=0}^\infty\binom{k}{i}x^i\sum_{j=0}^\infty(-1)^j\binom{-k}{j}x^{3j}\\ &=\sum_{j=0}^\infty\binom{k}{n-k-3j}(-1)^j\binom{-k}{j}\\ &=\sum_{j=0}^\infty\binom{k}{n-k-3j}\binom{j+k-1}{j}\tag3 \end{align} $$ That is, the coefficient of $x^n$ in $(1)$ is $$ \sum_{j=0}^{\left\lfloor\frac{n-k}3\right\rfloor}\binom{k}{n-k-3j}\binom{j+k-1}{j}\tag4 $$

Answer 2

In discrete mathematics, especially in genereting functions, there is a really nice pattern (exercise: prove that): $$\frac{C}{(1-\lambda x)^k} = C \sum_{n\ge 0} \binom{n+k-1}{k-1}\lambda ^n x^n$$ In your case take $t := x^{3k}$. Choosing certain $k$ can be helpful there.