Prove that for every $n\in\mathbb{N}$, $n^2$ is divisible by 3 or has a form $3k+1$? I tried to do this by induction, but it doesn't make any sense:  $n^2=3k$ or $n^2=3k+1$ 


*

*option: $(n+1)^2= 3k+2n+1$ 

*option: $(n+1)^2= 3k+2n+2$
Is there any other way on proving this problem?

For all $n$ natural number, $n = 3k$ or $n=3k+1$ or $n=3k+2$
When $n=3k$, $n^2=9k^2=3(3k^2)$, thus is divisible by 3
When $n=3k+1$, $n^2=9k^2+6k+1=3(3k^2+2k)+1$, thus is in the form of $3n+1$
When $n=3k+2$, $n^2=9k^2+12k+4=3(3k^2+4k+1)+1$, thus is in the form of $3n+1$
Thus, covering all the cases and finishing the proof
