Finding the Closed Form of a Multivariable Exponential Summation

Question

Here was a problem I thought of after seeing the 2017 HMMT #5:

For all positive integers $n$, what is the closed form of the summation of $\sum_{a+b+c+d=n}(3^a)(9^b)(27^c)(81^d)$, where $a, b, c,$ and $d$ are non-negative integers.

Here was the original 2017 HMMT #5.

https://hmmt-archive.s3.amazonaws.com/tournaments/2017/feb/algnt/problems.pdf

In that problem they just solved using casework, but I am unable to do that here. I tried breaking up the summations but was confused on how to do so. I think that generating functions may be the key to solving this problem but I don't know how to use them. How would I find the closed form of the summation I though of?

Answer 1

It is true you can solve this problem using generating function.

Let $(\alpha_1, \alpha_2, \alpha_3,\alpha_4) = (3,9,27,81)$, the sum at hand can be rewritten as

$$\Lambda_n \stackrel{def}{=} \sum_{\sum_{k=1}^4 e_k = n}\prod_{k=1}^4 \alpha_k^{e_k}$$ Multiply both sides by $z^n$ and sum over $n$ from $0$ to $\infty$, the corresponding OGF (oridinary generating function) equals to

$$\begin{align} \Lambda(z) \stackrel{def}{=} \sum_{n=0}^\infty \Lambda_n z^n &= \sum_{e_1=0}^\infty\sum_{e_2=0}^\infty\sum_{e_3=0}^\infty\sum_{e_4=0}^\infty \left(\prod_{k=1}^4 \alpha_k^{e_k}\right) z^{e_1+e_2+e_3+e_4}\\ &= \sum_{e_1=0}^\infty\sum_{e_2=0}^\infty\sum_{e_3=0}^\infty\sum_{e_4=0}^\infty \prod_{k=1}^4 (\alpha_k z)^{e_k}\\ &= \prod_{k=1}^4\sum_{e_k=0}^\infty (\alpha_k z)^{e_k} = \prod_{k=1}^4 \frac{1}{1 - \alpha_k z}\end{align} $$ Since the roots of $z$ in denominator of last expression ($\alpha_1^{-1},\alpha_2^{-1},\alpha_3^{-1}, \alpha_4^{-1}$) are distinct and simple, one can read off its partial fraction decomposition directly. The result is

$$\Lambda(z) = \sum_{k=1}^4 \frac{1}{1-\alpha_k z} \prod_{\ell=1,\ne k}^4 \frac{1}{1 - \alpha_\ell\alpha_k^{-1}} = \sum_{k=1}^4 \frac{\alpha_k^3}{1-\alpha_k z}\prod_{\ell=1,\ne k}^4 \frac{1}{\alpha_k - \alpha_\ell} $$ Expanding both sides and compare coefficients of $z^n$, one get

$$\begin{align} \Lambda_n &= \sum_{k=1}^4 \frac{\alpha_k^{n+3}}{\prod\limits_{\ell=1,\ne k}^n (\alpha_k - \alpha_\ell)}\\ &=\phantom{+} \frac{3^{n+3}}{(3-9)(3-27)(3-81)} + \frac{9^{n+3}}{(9-3)(9-27)(9-81)}\\ &\phantom{=} + \frac{27^{n+3}}{(27-3)(27-9)(27-81)} + \frac{81^{n+3}}{(81-3)(81-9)(81-27)}\\ &= \frac{-27\cdot 3^{n+3} + 39\cdot 9^{n+3} - 13\cdot 27^{n+3} + 81^{n+3}}{303264} \end{align} $$

As a doubt check, I have computed the first few $\Lambda_n$ by brute force

$$\Lambda_{1\ldots 6} = 120,10890,914760,74987451,6098153040,4946037697808153040$$

and above formula does produce the correct numbers.

Update

A web search indicate OEIS has recorded this sequence before (OEIS A226804). It also has a much simpler expression for $\Lambda_n$.

$$\Lambda_n = \frac{3^n(3^{n+1}-1)(3^{n+2}-1)(3^{n+3}-1)}{416}$$

Update 2

Playing around with an CAS, it seems above result can be generalized.

Instead of a 4-fold sum over $e_1,\ldots, e_4$ with $(\alpha_1,\ldots,\alpha_4) = (3, 3^2, 3^3, 3^4)$, we can consider a $p$-fold sum with $(\alpha_1,\ldots,\alpha_p) = (\alpha,\alpha^2,\ldots,\alpha^p)$. As far as I can test, we have $$ \sum_{\sum\limits_{k=1}^p e_k = n}\prod_{k=1}^p \alpha_k^{e_k} = \sum_{\sum\limits_{k=1}^p e_k = n}\alpha^{\sum\limits_{k=1}^p ke_k} = \alpha^n\prod_{k=1}^{p-1}\frac{\alpha^{n+k}-1}{\alpha^k-1} $$ This is a beautiful result but I am unable to derive it from first principle. See Calvin Lin's answer for a derivation.

Answer 2

Let's consider the general case where $a_i$ are distinct positive integers, and we want to find

$$ f(n, k, a) = \sum \prod_{\sum_{i=1}^k d_i = n} (a^i) ^ {d_i}. $$

• $ f( n, 1, a ) = a^n$, since there's only that one term.
• $ f(n, 2, a) $ can be split into terms which have $a^2$ involved, and terms which do not, giving us $f(n, 2, a) = a^2 f(n-1, 2, a ) + f(n,1,a)$. With an initial starting value of $f(0, 2, a ) = 1$, we can verify that $ f(n,2,a) = \frac{ a^n (a^{n+1} - 1) } { a- 1} $ by inducting on $n$.
• Likewise, $f(n, 3,a) $ can be split into terms which have $a^3$ involved, and terms which do not, giving us $f(n,3,a) = a^3 f(n-1, 3, a) + f(n,2,a)$. With an initial value of $f(0,3,a) = 1$, we can verify that $f(n,3,a) = \frac{ a^n (a^{n+1} - 1 ) ( a^ {n+2 } - 1 ) } { (a-1)(a^2 - 1 ) }$.
• More generally, via double induction, using the base case of $f(0,k,a) = 1$ and the recurrence

$$f(n,k,a) = a^k f ( n-1, k, a ) + f(n, k-1, a ), $$

we can show that

$$ f(n, k, a ) = \frac{ a^n \prod_{i=1}^{k-1} ( a^{n+i } - 1 )}{\prod_{i=1}^{k-1} a^i - 1}.$$

---

Notes

• I tried to generalize to arbitrary integers, but didn't seem to get that nice of a result.
• The 2 variable case leads to the Geometric Progression $ f( n | a, b ) = a^n \frac{ 1 - ( \frac{b}{a}) ^ {n+1 } } { 1 - \frac{b}{a}} $. You can see that when $ b = a^2$, we get a nice cancellation giving us the above formula.
• The 3 variable case can be conditioned in a similar manner as the above, but it's not immediately obvious that there is a nice simplification.