Let a(n) denote the number of ways of distributing candies to kids without distributing a multiple of m candies to any kid. Write generating function a() of the sequence {a(n)}.
I approached the question from the generating functions side, but no solution.
P.S I already submitted this empty, but i am too desperate to find the answer. Thanks for your help already
Edit:
i tried using $ 1/(1-x) - x^3/(1-x)$ and $ 1/(1-x) - 1/(1-x^3) + 1$
they both generate the same polynmial
(sum_(m=0)^∞ x^m) - (sum_(m=1)^∞ x^3m)
the problem starts at taking the k-th power of the sum and tried using wolframalpha and my self knowledge to find an infinite sum containing only single variable index.
i am always stuck at that point. i went through my special notes by my instructor's friend ( because he's more of a cryptographer and also he stated at the start that he also wants to improve). More importantly, i just cannot understand combinatorics(i mean counting problems, in that manner)
I would also appreciate any book that is easier to understand cuz I am more of a good listener than a reader. Still like reading.
Thanks for your help already
Go the other way around. The generating function of the number of candies one particular kid gets is:
$\begin{align*} c(z) &= \sum_{\substack{k \ge 0 \\ m \not\mid k}} z^k \\ &= \sum_{k \ge 0} z^k - \sum_{k \ge 0} z^{m k} \\ &= \frac{1}{1 - z} - \frac{1}{1 - z^m} \end{align*}$
If there are (n) kids, the generating function is:
$\begin{align*} g(z) &= c^n(z) \\ &= \left(\frac{1}{1 - z} - \frac{1}{1 - z^m}\right)^n \\ &= \sum_{0 \le k \le n} (-1)^{n - k} \binom{n}{k} \frac{1}{(1 - z)^k (1 - z^m)^{n - k}} \\ &= \sum_{0 \le k \le n} (-1)^{n - k} \binom{n}{k} \cdot \left( \sum_{r \ge 0} \binom{k + r - 1}{k - 1} z^r \right) \cdot \left( \sum_{s \ge 0} \binom{n - k + s - 1}{n - k - 1} z^{m s} \right) \\ &= \sum_{\substack{0 \le k \le n \\ r \ge 0 \\ s \ge 0}} (-1)^{n - k} \binom{n}{k} \binom{k + r - 1}{k - 1} \binom{n - k + s - 1}{n - k - 1} z^{r + m s} \end{align*}$
From this mess you want the coefficient of $z^N$ if you have $N$ candies:
$\begin{align*} [z^N] g(z) &= \sum_{\substack{0 \le k \le n \\ r \ge 0 \\ s \ge 0 \\ r + m s = N}} (-1)^{n - k} \binom{n}{k} \binom{k + r - 1}{k - 1} \binom{n - k + s - 1}{n - k - 1} \\ \end{align*}$
We could work some more on the summation condition $0 \le k \le n \wedge r \ge 0 \wedge s \ge 0 \wedge r + s m = N$ to get rid of $r$, but it is very unlikely that the resulting sum has any closed form solution.
The way forward is as outlined in Petkovsek et al "A = B". The relevant algorithms to reduce such sums to closed forms (or prove they don't exist) are too much work for hand computation, fortunately most computer algebra systems have them, possibly as add-ons.