To prove this by induction, we need to verify that the statement holds for the base case and show that if it holds for an arbitrary case $n=k$, then it also holds for the case $n=k+1$.

Base case: For $n=1$, the left side is $1^2$, and the right side is $\frac{1(2\cdot1^2+1)}{3} = \frac{3}{3} = 1$. So the statement holds.

Inductive step: Assume the statement holds for $n=k$:
$$1^2 + 2^2 + \ldots + (k-1)^2 + k^2 + (k-1)^2 + \ldots + 2^2 + 1^2 = \frac{k(2k^2+1)}{3}$$
Now, we need to prove it for $n=k+1$. We must add $(k+1)^2$ and $k^2$ to the sum, as we increment $n$ by 1, resulting in:
$$1^2 + 2^2 + \ldots + (k-1)^2 + k^2 + (k+1)^2 + k^2 + (k-1)^2 + \ldots + 2^2 + 1^2$$

From the inductive hypothesis, we already have $\frac{k(2k^2+1)}{3}$, so we need to add:
$$(k+1)^2 + k^2$$

Combining this with the inductive hypothesis, we get:
$$\frac{k(2k^2+1)}{3} + (k+1)^2 + k^2 = \frac{k(2k^2+1)+3(k+1)^2+3k^2}{3}$$
To prove that this equals $\frac{(k+1)(2(k+1)^2+1)}{3}$, we need to expand and simplify the numerator:
$$k(2k^2+1)+3(k^2+2k+1)+3k^2$$
$$= 2k^3 + k + 3k^2 + 6k + 3 + 3k^2$$
$$= 2k^3 + 6k^2 + 7k + 3$$
$$= (2k^3 + 4k^2 + 2k) + (2k^2 + 6k + 3)$$
$$= 2k(k^2 + 2k + 1) + (2k^2 + 6k + 3)$$
$$= \boxed{2k(k + 1)^2 + (2k + 1)(k + 1)}$$

To express this as a single fraction, we need it to match the format of $\frac{(k+1)(2(k+1)^2+1)}{3}$, which is:
$$\frac{(k+1)(2k^2+4k+2+1)}{3} = \frac{(k+1)(2k^2+4k+3)}{3}$$
$$= \frac{2k^3 + 6k^2 + 7k + 3}{3}$$

The two expressions are equivalent, thus the induction step is proved, and the expression that needs to be added to the left side when moving from $n=k$ to $n=k+1$ is:
$$\boxed{(k+1)^2 + k^2}$$