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.      

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.
