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.

$P(n)$ is the statement $1+3+\dots+(2n-1)=n^2$. To carry out a proof by induction, you must establish the base case $P(1)$, and then show that if $P(n)$ is true then $P(n+1)$ is also true.
In this problem, $P(n+1)$ is the statement $1+3+\dots+(2n-1)+(2n+1)=(n+1)^2$, because $2(n+1)-1=2n+1$. So by starting with $P(n)$ and adding $2n+1$ to both sides, you can prove $P(n+1)$.
