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.
 A: $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)$.
A: 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$.
A: 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?
A: Here is another proof, which does not rely on induction.
$\sum \limits_{i=1}^{N} (2i-1)=\sum \limits_{i=1}^{N} 2i-\sum \limits_{i=1}^{N}1$
Now, use the fact that $\sum \limits_{i=1}^{N}i=\frac{N(N+1)}{2}$. This can be proved a variety of ways, including induction.
$$2\sum \limits_{i=1}^{N} i-\sum \limits_{i=1}^{N}1=2\frac{N(N+1)}{2}-N=N^2+N-N=N^2$$
