0

thank you for taking the time to help me with the question. I am struggling to use proof by induction for this formula:

$$\sum_{k=0}^{n}k\times k! = (n + 1)! - 1$$

So far, I came up with:

$$S(n) = (n + 1)! – 1$$

Base case: When $n = 0$,

$(n + 1)! - 1 = (1)! - 1 = 0 = S(0)$, thus the base case is proved.

Inductive step: Suppose S$(n) = (n + 1)! – 1$, and n > 1 Then we have... $$S(n + 1) = ((n + 1) + 1)! - 1$$

I don't understand what is required of the proof by induction. What am I supposed to do?

Valentina
  • 123

1 Answers1

0

Using your function $S$ seems confusing to me - and I think it might be confusing you too. There are two functions at play here and we want to show that they are equal. In particular, let's define: $$S_1(n)=\sum_{k=0}^nk\times k!$$ $$S_2(n)=(n+1)!-1.$$ The goal is to prove that these two functions are equal. Your current proof looks like it's trying to show $S_2(n)=S_2(n)$ - which is probably why it's not working out so well.

So, you can start with the base case where $S_1(0)=S_2(0)=0$, which can you can by computation. Then, the inductive step is as follows

Suppose that $S_1(n)=S_2(n)$. Prove that $S_1(n+1)=S_2(n+1)$.

You can do this by relating the value of $S_1(n+1)$ to the value of $S_1(n)$ and the value of $S_2(n+1)$ to $S_2(n)$.

Milo Brandt
  • 60,888
  • How? I came up with:(k+1)! + (k + 1)(k + 1)! – 1 = (1 + k + 1)(k + 1)! – 1 = (k + 1)!(k + 2) – 1 = (k + 2)! - 1 – Valentina Dec 07 '14 at 18:36
  • That's pretty much what you need; you just need to label it. The rightmost expression is $S_2(k+1)$, which is good. The leftmost equation you have could be written as $[(k+1)!-1]+(k+1)(k+1)!$ which is $S_2(k)+(k+1)(k+1)!$, but by inductive hypothesis that $S_2(k)=S_1(k)$ and thus this is the same as $S_1(k)+(k+1)(k+1)!$ - but hey, $(k+1)(k+1)!$ is just the next term of the sum $S_1(k)=\sum_{i=0}^{k}k\times k!$ so that side equals $S_1(k+1)$. Therefore, after this relabeling, you have $S_1(k+1)=S_2(k+1)$ - which is what you were after. – Milo Brandt Dec 07 '14 at 18:46