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.

The idea of a proof by induction is to


*

*Show that the Proof $P$ holds for $P(1)$

*Assume the proof holds for $P(k), \ k \in N$

*Show that the proof holds for $P(k + 1), \ k \in N$


The reason this works is because if the proof works for $P(1)$, and we know that the proof will work for all $k + 1$, we can say $k = 2$ and have the proof work for $P(2)$. Repeating this process, we can have the proof work for all $P(n), n \in N$
Considering this, your $P(n)$ was that
$$P(n): 1 + 3 + \ldots + (2n - 1) = n^2$$
Using this framework, can you try the proof out again?
