1
$\begingroup$

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.

enter image description here

$\endgroup$
1
$\begingroup$

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)$$

$\endgroup$
0
$\begingroup$

My understanding is that- In your first underline they are considering the sum $1+2+3..$ till $(k +1)$ . This series can be written as $1+2+3+...+(k+1)$ = $1+2+3+...+k+(k+1)$.

In the second underline, they substituted $ 1+2+3+.. +k$ as $\frac{k(k+1)}{2}$, which was derived from the "Inductive Hypothesis".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.