<s>[INST] Let $k$ be an odd positive integer. Prove that $(1+2+3...+n)|(1^k+2^k+3^k+...+n^k)$ for all positive integers $n$. Problem:Let $k$ be an odd positive integer. Prove that $(1+2+3...+n)|(1^k+2^k+3^k+...+n^k)$ for all positive integers $n$.
My Attempt: Proof (By Induction on $k$): Let $P(k)$ be the proposition that $(1+2+3...+n)|(1^k+2^k+3^k+...+n^k)$ for all positive integers $n$ when $k$ is odd. Then $P(1)$ and $P(3)$ are trivially true. So for $k\geq 5$, we assume that $P(k)$ holds. We would like to show that $P(k+2)$ also holds. In order to do that consider the following sums 
$$1^{2}(1^k+2^k+3^k+...+n^k)=1^{k+2}+2^k+3^k+...+n^k$$
$$2^{2}(1^k+2^k+3^k+...+n^k)=2^2*1^k+2^{k+2}+2^2*3^k+...+2^2*n^k$$
$$..$$
$$n^2(1^k+2^k+3^k+...+n^k)=n^2*1^k+n^2*2^k+n^2*3^k+...+n^{k+2}$$
Note that $$1^2(1^k+2^k+3^k+...+n^k)+2^2(1^k+2^k+3^k+...+n^k)+...+n^2(1^k+2^k+3^k+...+n^k)\equiv 0\pmod {\frac{n(n+1)}{2}}$$ 
Therefore, if we denote $\sum_{i=1}^{n}i^2=s$, then  
$(t)(1^k+2^k+3^k+...+n^k)-t+\sum_{i=1}^{n}i^{k+2}\equiv 0\pmod {\frac{n(n+1)}{2}}$ which implies that $P(k+2)$ holds. Hence by PMI we are done.
Now I am a bit hesitant in convincing myself whether this proof is correct or not. This is because I have never seen induction performed in this manner. Any reasons as to why this argument falls would be much appreciated.      
 [/INST] Your identity is wrong so your solution is wrong.
Here is one way to attempt the problem. We know $1+2+ \cdots +n=\dfrac{n(n+1)}{2}$ and $\gcd (n,n+1)=1$. We consider following two cases:
Case 1. If $n$ is even then there are $n/2$ pairs of $i^k,(n-i+1)^k$ and see that $n+1 \mid i^k+(n-i+1)^k$ since $k$ is odd. Thus, $n+1 \mid 1^k+ \cdots + n^k$. 
Next, we group $i^k,(n-i)^k$ then there are $(n-2)/2$ pairs and there is two numbers $n^k,(n/2)^k$ left. Note that $n \mid i^k+(n-i)^k$ since $k$ is odd so $$n/2 \mid \sum_{i=1}^{(n-2)/2} \left( i^k+(n-i)^k \right)+n^k+(n/2)^k.$$
Since $\gcd \left( n/2,n+1 \right)=1$ so $\dfrac{n(n+1)}{2} \mid 1^k+ \cdots + n^k$ or $1+2+ \cdots +n \mid 1^k+2^k+ \cdots + n^k$.
We do the similar thing to the case $n$ is odd.
</s>