Proving by induction that $\frac{n(n + 1)(2n + 1)}{6} = 0^2 + 1^2 + 2^2 + 3^2 + ... + n^2$ Note: I am asking this question as a simple introductory question to proofs by induction, to which I will give also my formal answer (which should be correct, if not, please comment) for future visitors of this website.
I know that to prove something by induction, we need formally 3 steps (2, if we considere inductive hypothesis and inductive step together):


*

*Base case or basis:
We determine what is the base case for our statement $P(n)$, and we immediately prove it.

*Inductive hypothesis:
We assume our statement $P(n)$ is true for $n$.

*Inductive step:
We try to prove that our statement is also true for $P(n + 1)$. If we can prove that, we can also prove that our statement is true for $n + 2$ (we don't need to do it), and so on.
This step is usually the most difficult part, because it involves some algebraic manipulation, or some imagination in some way. For this last reason, it might be helpful watching other similar proofs by induction to solve the current one.
For example, suppose our $P(n)$ is the following:
$$\frac{n(n + 1)(2n + 1)}{6} = 0^2 + 1^2 + 2^2 + 3^2 + ... + n^2$$
which is basically saying that the sum of all squares of the natural numbers from $0$ to $n$ can be determined by the formula on the left side of the equation.
How would we prove $P(n)$ is true for all $n \in \mathbb{N}$?
For more information about the proof by induction, see the Wikipedia page about induction called Mathematical induction.
 A: Like any proof by induction, we need to go through all 3 steps cited above for our example:


*

*Basis:
Considering the first natural number is $1$, then our base case is $n = 1$, because we want to prove $P(n)$ for all natural numbers (It would also not make much sense to make the sum of $0$ members of the sequence).
What we need to do is simply replacing $n$ with $1$s in our of formula, and check if the result is equals to the sum of the squares of the numbers until $1$ ($0^2  + 1^2 = 1$). So we have:
$$\frac{1(1 + 1)(2 \cdot 1 + 1)}{6} = 0^2 + 1^2  = 1$$
simplifying the left side expression, we have:
$$\frac{(2)(3)}{6} = 0^2 + 1^2  = 1$$
which is clearly a true statement.

*Inductive hypothesis:
Here, we assume $P(n)$ is true for $n$, so we assume that $$\frac{n(n + 1)(2n + 1)}{6} = 0^2 + 1^2 + 2^2 + 3^2 + ... + n^2$$ is true.

*Inductive step:
Now, we have to prove $P(n + 1)$ is also true. One usually technique is replacing $n$ with $n + 1$ in our statements, so we have:
$$\frac{(n + 1)((n + 1) + 1)(2(n + 1) + 1)}{6} = 0^2 + 1^2 + 2^2 + 3^2 + ... + n^2 + (n + 1)^2$$
Note that I have also added a new term for the right sequence $n + 1$, since our formula determines now the sum of all squares from $0$ to $n + 1$.
Now, you might think, how can we solve this? At this point, it might be useful to use something that you assumed, for example $P(n)$ for our example. In fact, you know that $$\frac{n(n + 1)(2n + 1)}{6} = 0^2 + 1^2 + 2^2 + 3^2 + ... + n^2$$
Can we see something that could be replaced in our $P(n + 1)$ with something from our $P(n)$? Yes, we could replace the sequence: $$0^2 + 1^2 + 2^2 + 3^2 + ... + n^2$$ with the corresponding formula: $$\frac{(n + 1)((n + 1) + 1)(2(n + 1) + 1)}{6} = \frac{n(n + 1)(2n + 1)}{6} + (n + 1)^2$$
If you solve the above statement, you will arrive at a true statement, something like $1 = 1$, which confirms that our statement is also true for $n + 1$, and that confirms, by induction, that $P(n)$ is valid for all $n \in \mathbb{N}$.
