Finding the Closed Form of a Multivariable Exponential Summation 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?
 A: 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.

