I have two solutions to Problem 3, one via recursion and one via generating functions.

CANBANKAN wrote: Remark: Can the $O(n^{k-2})$ be improved to $O(1)$? As already mentioned elsewhere, this is clearly not possible and indeed $\mathcal{O}(n^{k-2})$ is sharp as can be seen already in the simplest case $a_1=\dots =a_k=1$ where $S(n)=\binom{n+k-1}{k-1}$.

Here's a less explicit solution. Say two functions $P,Q$ are approximately equal if $\frac{P(x)}{Q(x)} \rightarrow 1$ for big enough $x$. Claim: For a fixed $k$, there exists a polynomial $P_k(x)$ such that $S(n)$ and $P_k(n)$ are approximately equal. Proof: Induct on the value of $k$, for $k = 1$ we just have $P_1(x) = 1$. Now suppose we go from $k$ to $k+1$. Denote $S(n)$ as the thing for $k$ and suppose by inductive hypothesis we have $(1+\epsilon)P_k(n) > S(n) > P_k(n)$ for all $n > M$ for any $\epsilon > 0$. WLOG assume $\gcd(a_1, a_2, \cdots, a_{k+1}) = 1$ and until $a_k$ it is $d$. Then we fix $x_{k+1} \equiv \frac{n}{a_{k+1}} \pmod{d}$, say this residue class is $r$ and let $C = ra_{k+1}$. Then we have the number of ways to write $n$ (say $W$) is $S(n-C) + S(n-2C) + S(n-3C) + \cdots $. But for sufficiently large $n$, this means $(1+ \epsilon) (P_k(n-C) + P_k(n-2C) + \cdots + O(1)) > W > P_k(n-C) + P_k(n-2C) + \cdots + O(1)$. But the right hand side is approximately equal to some polynomial, for example $\int_{0}^{\frac{n}{C}} P_k(xC) \cdot dx$ should work. So we can set this as $P_{k+1}(x)$ and induct. $\square$ To finish, note that for big enough $n$, we have $(1-\epsilon)P_k(n)< S(n) < (1+\epsilon)P_k(n)$. So it suffices to show that $(1+\epsilon)P_k(n+1) < 2(1-\epsilon)P_k(n)$, which is true for any nonconstant polynomial with positive leading coefficient on taking $\epsilon$ small enough and $n$ big enough, so we're done. $\blacksquare$

Redacted.

L567 wrote: Here's a less explicit solution. Say two functions $P,Q$ are approximately equal if $\frac{P(x)}{Q(x)} \rightarrow 1$ for big enough $x$. Claim: For a fixed $k$, there exists a polynomial $P_k(x)$ such that $S(n)$ and $P_k(n)$ are approximately equal. Proof: Induct on the value of $k$, for $k = 1$ we just have $P_1(x) = 1$. Now suppose we go from $k$ to $k+1$. Denote $S(n)$ as the thing for $k$ and suppose by inductive hypothesis we have $(1+\epsilon)P_k(n) > S(n) > P_k(n)$ for all $n > M$ for any $\epsilon > 0$. WLOG assume $\gcd(a_1, a_2, \cdots, a_{k+1}) = 1$ and until $a_k$ it is $d$. Then we fix $x_{k+1} \equiv \frac{n}{a_{k+1}} \pmod{d}$, say this residue class is $r$ and let $C = ra_{k+1}$. Then we have the number of ways to write $n$ (say $W$) is $S(n-C) + S(n-2C) + S(n-3C) + \cdots $. But for sufficiently large $n$, this means $(1+ \epsilon) (P_k(n-C) + P_k(n-2C) + \cdots + O(1)) > W > P_k(n-C) + P_k(n-2C) + \cdots + O(1)$. But the right hand side is approximately equal to some polynomial, for example $\int_{0}^{\frac{n}{C}} P_k(xC) \cdot dx$ should work. So we can set this as $P_{k+1}(x)$ and induct. $\square$ To finish, note that for big enough $n$, we have $(1-\epsilon)P_k(n)< S(n) < (1+\epsilon)P_k(n)$. So it suffices to show that $(1+\epsilon)P_k(n+1) < 2(1-\epsilon)P_k(n)$, which is true for any nonconstant polynomial with positive leading coefficient on taking $\epsilon$ small enough and $n$ big enough, so we're done. $\blacksquare$ I had the same solution on contest up to a very hasty writeup with some obvious details underexplained. Got a 0 and they didn't want to give even a single point on coordination. IZhO is a scam.

Define $f(n,[a_1,a_2,\cdots , a_k])$ as the number of solutions to $a_1x_1+a_2x_2+\cdots a_kx_k=n$. Treat this as a function in $n$. Main claim: For any constants $c,t$ and $a_1,a_2,\cdots a_k$ we have $tf(n-ca_1,[a_2,\cdots, a_k])<f(n,[a_1,a_2,\cdots a_k])$ for all sufficiently large $n$, assuming $f(n,[a_1,a_2,\cdots a_k])>0$ for sufficiently large $n$. Intuitively, the number of solutions with $x_1=c$ should eventually take up a negligible proportion of all solutions. Proof. We use induction on $k$ with base case $k=2$. The number of solutions to $n-ca_1=x_2a_2$ is obviously $\le 1$, while the number of solutions to $n=x_1a_1+x_2a_2$ is linear (we can subtract $a_2$ from $x_1$ and add $a_1$ to $x_2$). Hence the base case is done. Suppose the statement is true for $k-1$, consider when there are $k$ numbers in the list. Consider the solutions to $n-ca_1=x_2a_2+x_3a_3+\cdots+x_ka_k$. By the induction hypothesis, the number of solutions with $x_2<N$ for some constant $N$ becomes a negligible proportion of the solutions (say $\frac{1}{x}$ of them). For the other solutions (with $x_2>N$), we can map each solution to $\frac{N}{a_1}$ solutions of $n=x_1a_1+x_2a_2+x_3a_3+\cdots+x_ka_k$ (taking $x_1=c+ka_2, x_2=x_2=x_2-ka_1$). Hence for sufficiently large $n$, $f(n,[a_1,a_2,\cdots, a_k])$ is at least $\frac{1}{x}+\frac{x-1}{x}\left(\frac{N}{a_1}\right)$ times of $f(n-ca_1,[a_2,a_3,\cdots a_k])$. Since $x\to \infty$ as $n\to \infty$ for any $N$ we choose, $\frac{1}{x}+\frac{x-1}{x}\left(\frac{N}{a_1}\right)$ is unbounded, i.e. we have shown that the original claim is true. Finish: Consider some solution ($y_i$s are integers) to $a_1y_1+a_2y_2+\cdots a_ky_k=1$. For any solution to $n+1=a_1x_1+a_2x_2+\cdots a_kx_k$, if $|x_i|>|y_i|$ for all $i$ we can map this to a distinct solution for $n=a_1x_1+\cdots a_kx_k$ by subtracting $y_i$ from each $x_i$. For the other solutions (with some $|x_i|\le |y_i|$), from the main claim this will eventually form a negligible part of the solutions. Hence, $S(n+1)$ will eventually be $<(1+\epsilon)S(n)$ for any $\epsilon<0$, completing the question.