So I have an example of a proof that my teacher used induction to solve, but I'm having trouble understanding the inductive step in the second slide. So I get the part where they substitute k+1 in the formula, but I don't understand where the 1+2+…+ 𝒌 +(𝒌 +1) came from and how that managed to turn into the equation in my 2nd underline?
Like the k + (k+1) portion doesn't look like it matches the original formula, and I'm confused because it looks like they substituted n with k instead of k + 1 like it was stated at the beginning of the second slide? I also don't really understand recursion, so I'd appreciate if someone explained the steps behind that transition to me as well.
Best Answer
When they write $1+2+\ldots + (k+1)$, they mean summing up every positive integer up to $k+1$. The integer before $k+1$ is $k$.
Hence $$1+2+\ldots + (k+1) =(1+2+\ldots + k)+ (k+1)\tag{1} $$
We already know that $1+2+\ldots + k = \frac{k(k+1)}{2}$ by the induction hypothesis, substitute this into $(1)$ and we have
$$(1+2+\ldots + k)+ (k+1)= \frac{k(k+1)}{2}+(k+1)$$