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?

Because you wanted to proceed by induction ...
Base case: $0^3 = 0$ is divisible by 3
For any $n$, we have 2 cases.
First take $(n + 1)^2 = n^2 + 2n + 1$
Case 1: $n^2$ is divisible by 3
Let $n = 3k$. What can we conclude?
Case 2: $n^2$ is $3k + 1$. 
$$ n^2 + 2n + 1 = n^2 - 1 + 2(n + 1) = (n - 1)(n + 1) + 2(n + 1)$$
We know $n$ is even as $n^2$ is even (fundamental theorem of arithmetic). 
Then if $n + 1$ is divisible by 3, we are done.
If $n + 1$ is not, then because $n$ is even, for odd $m$, $n + 1 = 3m + 2$. 
$$2(n + 1) = 2(3m + 2 + 1) = 2(3m + 3) = 6m + 6$$.
And you can see that it is divisible by 3.
