Understanding a proof by induction In the following proof by induction:
Problem: Prove by induction that $1+3+ \ldots+ \ (2n-1)=n^2$
Answer:
a) $P(1)$ is true since $1^2=1$
b)Adding $2n+1$ to both sides we obtain:
$$
1+3+..+(2n-1)+(2n+1)=n^2+2n+1=(n+1)^2
$$
Why $2n+1$ ? Where does this come from?
And how does knowing that
$$
1+3+ \ldots +(2n-1)+(2n+1)=(n+1)^2
$$
prove anything?
Appreciate any light, thanks.

Suppose that the assertion holds for all integers less than or equal to $n$. We want to show that it holds for $n+1$. By assumption, we have
$$
1+3+\cdots+(2n-1) = n^2
$$
Adding $(2n+1)$ to both sides, we have
$$
1+3+\cdots+(2n-1)+(2n+1) = n^2 + 2n+1 = (n+1)^2
$$
Hence, we have that
$$
1+3+\cdots+(2(n+1)-3)+(2(n+1)-1) = (n+1)^2
$$
So the assertion holds for $n+1$. This proves that the assertion holds for all $n$.
