induction
My textbook provides the following proof that giving the sum of the first $n$ odd numbers is equal to $n^2$ then it is true for all $n$.
I don't understand the part where it "adds $2k+1$ to both sides" and ends up with $(k+1)^2$.
I looked up another proof of the same problem that made a lot more sense to me, hoping it would help me understand the first one but I still don't know how to square what I'm seeing in my textbook.
What is induction?
At its core, induction is this statement:
Take a set $S$. If $1 \in S$, and $k \in S$ implies that $k + 1 \in S$, then all natural numbers are in $S$.
Intuitively, this is pretty obvious. Assume both hypotheses: that $1 \in S$ and $k \in S \implies k + 1 \in S$.
That clearly wasn't a formal proof that induction is valid, but it's a good place to start your intuition. No matter what natural number we start at, we can "step back" by one until we hit $1$, which we know is true.
Wait, how'd sets get in there?
Normally, people don't talk about sets when it comes to induction. Usually, it's about propositions. But the two are equivalent, consider the set $S = \{ n \mid P(n) \}$ or the proposition $P(n) = n \in S$. If you're working with propositions, induction is stated as:
Take a proposition $P$. If $P(1)$ is true, and $P(k)$ implies that $P(k+1)$, then $P(n)$ is true for all $n \in \mathbb{N}$.
How do we do inductive proofs?
Like any conditional statement, all you need to do is prove the two hypotheses:
or for propositions,
The confusing part
The recursive step sometimes confuses people. "Aren't we assuming what we want to prove?" Not quite. Here, a precise understanding of conditional statements is required. If I say, "If today is Friday, tomorrow is Saturday", I am not saying that today is Friday. I am only saying that, if we can show today is Friday, then we know tomorrow is Saturday.
It is the same with the recursive step. We are proving: "if $P$ is true for $k$, then it is also true for $k + 1$". We have not said anything about whether or not $P(k)$ is true!
Additionally, we are not assuming $P$ is true for all $k$, we are only assuming it to be true for a particular $k$. In notation, the recursive step is:
$$\forall k \in \mathbb{N} \ (P(k) \implies P(k + 1))$$
Finally, induction is not the process of proving those two statements. Those can be proved like any other statement. Induction is the statement "if those two statements are true, then $P$ is true for all natural numbers".
An example
We want to show that $\sum_{i = 1}^n i = \frac{n(n+1)}{2}$. (In terms of sets, this would be "all natural numbers are in the set $\{ n \mid \sum_{i = 1}^n i = \frac{n(n+1)}{2} \}$, but usually, the proposition syntax is easier).
"$P$ is true for $1$" is pretty easy to see, just plug it in and check.
The recursive case isn't much harder. Assume that $\sum_{i = 1}^k i = \frac{k(k + 1)}{2}$ is true for some $k$. Then, by adding $k + 1$ to both sides, we get $\sum_{i = 1}^{k+1} i = \frac{(k + 1)(k + 2)}{2}$. So, $P(k) \implies P(k+1)$.
Since $P(1)$ and $P(k) \implies P(k + 1)$, then by induction, $P(n)$ is true for all $n$.
Strong induction
The induction described above is called "weak induction". Strong induction is when your recursive hypothesis is replaced with "if $P$ is true for all $i$ less than $k$, then $P$ is true for $k$". The justification is similar, except to prove that $P(k)$ is true, we can look at any $i$ less than $k$, not just $k - 1$. It is called strong because your hypothesis is stronger, you can look at more $i$.
Sometimes this format is easier to use than weak induction. As an example, we show that all natural numbers can be written as $2^a m$, where $m$ is odd. The base case is easy, $1 = 2^0 \cdot 1$.
For the recursive case: let $k \in \mathbb{N}$ and assume that $P(i)$ is true for all $i < k$. If $k$ is odd, we are done. If not, there is some $i < k$ such that $2i = k$. By hypothesis, $i = 2^a m$ for some $a, m$, where $m$ is odd. Thus, $k = 2^{a + 1} m$.
Since $P(1)$ and $\forall i < k \ P(i) \implies P(k)$, by strong induction, $P(n)$ is true for all $n \in \mathbb{N}$. This would be difficult with weak induction.
Why is it valid?
Above, an intuitive argument for induction was shown. But in math we like to prove things. To do so, we introduce the "well-ordering principle": all non-empty subsets of $\mathbb{N}$ have a smallest element.
The well-ordering principle, weak induction, and strong induction are all equivalent!
Either you can take one of them as an axiom, or you can prove one by whichever construction of $\mathbb{N}$ you have. Then, there are pretty simple proofs to show the equivalence of the three.
Well-ordering implies weak induction: Let $S$ be a set, where $1 \in S$, and $k \in S \implies k + 1 \in S$. Let $T = \mathbb{N} \setminus S$, that is, all natural numbers not in $S$. Assume $T$ is non-empty. By well-ordering, it has a least element, $k$. Clearly it can't be $1$, because $1 \in S$. So it must be greater than $1$, and so $k - 1 \in \mathbb{N}$. Since $k$ is the smallest element in $T$, $k - 1$ can't be in $T$, meaning $k - 1 \in S$. But by assumption, that implies $(k - 1) + 1$ is in $S$, and so $k \in S$, which contradicts that $k \in T$. Therefore, $T$ was empty after all, and so $\mathbb{N} \subseteq S$.
Weak induction implies strong induction: Let $P(k)$ be a proposition where $P(1)$ and if $P(i)$ for all $i < k$, then $P(k)$. Let $Q(n)$ be the proposition "$P(k)$ is true for all $k < n$". We will use weak induction on $Q$. First, note that $Q(1)$ is true. Next, assume that $Q(n)$ is true. That means that $P(i)$ is true for all $i < k$, and so by our initial description of $P$, $P(n + 1)$ is true. But since $Q(n)$ and $P(n + 1)$ are true, $Q(n + 1)$ is true as well. Therefore, the conditions for weak induction are satisfied, and $Q(n)$ is true for all $n$. This clearly means that $P(n)$ is true for all $n$ as well.
Strong induction implies well-ordering: Let $P(n)$ be the proposition "if $n \in S$, then $S$ has a least element". Clearly it is true for $1$, because if $1 \in S$, then $1$ is the least element of $S$. For the recursive step, assume that $P(i)$ is true for all $i < k$. Then we wish to show that $P(k)$ is true. Let $k \in S$. If $k$ is the smallest element, then we are done. If not, then there is some $i < k$ such that $i \in S$. Thus, $P(i)$ is true, and so $S$ has a smallest element. By strong induction, if there is any $n \in S$, then it has a least element (this is where the "non-empty" part crops up).
Which one of these proofs you need depends on what your construction of $\mathbb{N}$ is or what axioms you have.
We need to prove that $$ \sum_{k=1}^nk2^k=(n-1)(2^{n+1})+2 $$ Consider $P_1$ where $k=1$. Left Hand Side (LHS) and Right Hand Side (RHS) are evaluated as follows. $$\sum_{k=1}^1k2^k=1\times2=2\quad\quad\quad\quad\quad\quad(1-1)(2^2)+2=2$$
Now, we assume that $P_m$ holds for some natural number $m$. (The trick here is that you will need to use this result later.) $$ \sum_{k=1}^mk2^k=(m-1)(2^{m+1})+2 $$
It must be shown that $P_{m+1}$ holds too. Let us prove it. The RHS, which is relatively easier is $$ \begin{align*} [(m+1)-1](2^{m+2})+2&=m(2^{m+2})+2 \end{align*} $$ What we need to do is to show that the LHS has this form:
$$ \begin{align*} \sum_{k=1}^{m+1}k2^k&=\sum_{k=1}^mk2^k+(m+1)2^{m+1}\\ &=(m-1)(2^{m+1})+2+(m+1)2^{m+1}\\ &=(m-1)(2^{m+1})+(m+1)2^{m+1}+2\\&=(2m)(2^{m+1})+2\\ &=m(2^{m+2})+2 \end{align*} $$ Since $P_1$ true, $P_m$ true $\rightarrow P_{m+1}$ true, by Mathematical Induction, $P_k$ true for $k=1, 2, \cdots$
Best Answer
Since you are trying to proof the assertion with the help of induction you have to first show that $P(1)$ is true. In the second step (induction step) you have to show that $P(k+1)$ is true, where you assume that $P(k)$ is true. The author realized that the term $1 + 3 + \dotsc + 2k-1$ is obviously part of the term $1 + 3 + \dotsc + 2k-1 +2k +1$. Since the author knows that $1 + 3 + \dotsc + 2k-1=k^2$ (by the assumption "$P(k)$ is true") he just added $2k+1$ on both sides and calculated that the right hand side to get $k^2+2k+1=(k+1)^2$, which shows that $P(k+1)$ is true.
A better way would be the following: Let us assume that $P(k)$ is true for a $k\in \mathbf N$. Let us show that $P(k+1)$ is true aswell. Therefore we have to show that $1 + 3 + \dotsc + 2k-1 +2k +1 =(k+1)^2$. We have by the induction hypothesis $$1 + 3 + \dotsc + 2k-1 +2k +1= k^2 +2k+1$$ and since the right hand side equals $(k+1)^2$, we are done.