If there exists a sequence of integers $a_0,a_1,\ldots$ such that $a_n=\frac{a_{n-1}+n^k}{n}, \quad \forall n \ge 1$, then $3 \mid (k-2)$. Let $k$ be a positive integer. Show that if there exists a sequence of integers
$a_0,a_1,\ldots$ such that
$$a_n=\frac{a_{n-1}+n^k}{n}, \quad \forall n \ge 1,$$
then $3 \mid (k-2)$.
ATTEMPT:
I have tried for $k=2$ and found a sequence of integers $(a_n)$ with $a_n=n+1$ for any nonnegative integer $n$ that satisfied the reccurence relation and implies $3 \mid k-2$.
Let there be a sequence $a_0,a_1,a_2,\ldots$ such that
$$a_n=\frac{a_{n-1}+n^k}{n}, \quad \forall n \ge 1.$$
Suppose for the contrary that $3 \nmid k-2$. It means that $k=3t$ or $k=3t+1$, for some positive integer $t$.
CLAIM: $a_n = \frac{a_0+1+2^k+2\cdot 3^k+ \cdots + (n-1)!n^k}{n!}$ for any integer $n \ge 1$.
PROOF OF CLAIM: Easy back substitution to $a_n. \quad \Box$
Now, by the claim, there are $5$ cases that should be considered on $a_0$.
First, let's consider the case when $k=3t$, for some positive integer $t$.

*

*$a_0>0$ and $a_0$ is even.

In this case, let $a_0=2s$ for some positive integer $s$. Consider $n=2$. Then
$$a_2 = \frac{a_0+1+2^k}{2!}=\frac{2s+1+2^{3t}}{2},$$
which is, clearly, not an integer, a contradiction with assumption that $a_2$ is an integer which is in the sequence of integer $a_0,a_1,a_2,\ldots$.


*$a_0>0$ and $a_0$ is odd.

Let $a_0=2m+1$ for some nonnegative integer $m$. Notice that
$$a_3=\frac{2m+2+2^{3t}+2\cdot 3^{t}}{6}.$$
I got stucked here. How to conclude that $a_3$ is not being in the sequence of integers?


*$a_0<0$ and $a_0$ is even.

*$a_0<0$ and $a_0$ is odd.

*$a_0=0$.

 A: Some hints: (Not a full answer)
If this is a series of integers, and the RHS is $(a_{n-1} + n^k)/n$, what must $a_{n-1}$ be divisible by? (Except in edge cases, which I'm sure exist.)
Consider trying out the simplest cases that are predicted to work or not work: if $3\mid k-2$, then $k=1$ ought to fail, and $k=2$ ought to succeed. Note though that we don't know for sure what $a_0, a_1$ are.
Try some easy values of $a_0$ and see if you can find a pattern, then use that pattern to figure out how to create a proof. This look like direct proof or contradiction are the best bets.

All right, let's see if I can give a full answer. First, let's be absolutely clear about what we're trying to prove. Calling a sequence fitting this recursion $A_k$, we want:
$$\exists A_k \implies 3 \mid k-2 \implies k \equiv 2 \pmod 3$$
Note the lack of a reverse implication. As formulated, in fact, it would be sufficient to prove that no such sequence exists. We don't have to find a sequence for all $k \equiv 2 \pmod 3$ because nothing says every such value generates a sequence.
Now, the reality is this: exactly one infinite sequence exists that fits these parameters, and that sequence has $k = 2, a_0 = 1$. And you might have seen this sequence before: its first ten terms are $(1,2,3,4,5,6,7,8,9,10)$.
With this in mind, let's see if we can prove what we actually want to prove.

Let's rewrite the recurrence slightly:
$$a_n = \frac{a_{n-1}}{n} + n^{k-1}$$
There are two takeaways from this:

*

*First, $a_1 = a_0 +1$ no matter what $k$ is.

*Second, it's clear that $a_n \in \mathbb{Z} \iff n \mid a_{n-1}$.

Therefore in order for the sequence $A$ to exist, there must be another sequence of integers $B = (b_0, b_1, b_2, \cdots)$ such that $A = (b_0, 2b_1, 3b_2, \cdots nb_{n-1}, (n+1)b_n \cdots)$. Sequence $B$ is just the quotients of the members of sequence $A$ with increasing $n$.
But we just said $a_1 = a_0 + 1$, which implies $2b_1 = b_0 + 1$
We can replace $A$ completely, and rewrite the recurrence as:
$$(n+1)b_n = \frac{nb_{n-1}}{n} + n^{k-1} = b_{n-1} + n^{k-1}$$
$$b_n = \frac{n^{k-1} + b_{n-1}}{n+1}$$
With the kicker that $b_n$ is an integer, so $n+1 \mid n^{k-1} + b_{n-1}$. And that has to be true for every value of $b_n$. How can we guarantee that?
Well, one obvious way is if $k-1 = 1$ and $b_{n-1}=1$. Then we just have $(n+1)/(n+1) = 1 = b_n$, so $b_n = 1$ for all $n$. This, of course, is the sequence described earlier.
OK, but can we guarantee that condition any other way? No, we can't. Let's take that last equality and make it a bit more generic:
$$t = \frac{n^r + s}{n+1}$$
This is now a polynomial division--we need $n+1$ to be a factor of $n^r+s$. But the set of values of $r,s$ for which $n^r + s$ can even be factored is... tiny. If $r$ is even, there's no factorization at all in the integers. If $r$ is odd, $n^r + s$ can be factored iff $s = q^r$. That factorization is:
$$n^{r} + q^{r} = (n+q)(n^{r-1} - n^{r-2}q + n^{r-3}q^2 - \cdots + q^{r-1})$$
Note the lack of an $n+1$ factor unless $s = q = 1$. But now consider the case where we have $t = (n^3 + 1)/(n+1)$. This factorizes, and $t = n^2 - n + 1$. But then $b_{n-1} = 1 \implies b_n = n^2 - n + 1 \ne 1$. So in the next recursion, there's no factorization available, and we are back to the original problem. This holds in parallel fashion for higher odd exponents.
Therefore we conclude that the only values for which this sequence contains only integers is the instance with $a_0 = 1, k=2$. Hence the one sequence that does exist has $3 \mid k-2$, and we've proven the original proposition.
Looking through this, I could have formalized better, but there's a lot of explanation throughout. Hopefully you can follow the logic; feel free to ask questions (and of course others, feel free to point out holes).
