I\'m doing Algorithms and I\'m having a little trouble with mathematical inducti

Question

I'm doing Algorithms and I'm having a little trouble with mathematical induction. I understand the basics of mathematical induction, namely I can understand the following:

The induction base is the proof that the statement is true for n = some initial value.

The induction hypothesis is the assumption that the statement is true for an arbitrary n>= some initial value.

The induction step is the proof that if the statement is true for n, it must also be true for n + 1.

But... even knowing this I have troubles with induction problems. my homework for Algorithms is a bunch of mathematical induction problems and I'm stuck on the last set. This is one of the ones that I'm stuck on.

My work looks a little like this:

Induction base: For n = 1,

Induction hypothesis:

Assume that for an arbitrary positive integer n...

Induction step:

Show that...

To that end...

This is what I have so far. But, I'm not completely sure if it's right... I'm really bad at these, I can only do simple ones. Either way, I thought I would ask someone in computer science about it. I'm sure it has to do with writing recursive algorithms, so even code, as long as it's explained, would be helpful. Thank you!

Explanation / Answer

To prove: k=1n   k (k!) = (n+1)! -1

Basis: let n=1 => k=11 k(k!) = (1)(1!) = 1 ; (n+1)!-1 = (1+1)!-1 = 2! -1 =2 -1 =1; LHS = RHS. Hence basis is true.

Assume k=1n   k (k!) = (n+1)! -1 is true for n numbers.(Eqn. 1)

To prove: k=1n+1 k (k!) = [(n+1)+1]! -1 = (n+2)! - 1

k=1n+1 k (k!) = k=1n   k (k!) + n+1n+1 k (k!) = k=1n   k (k!) + (n+1)(n+1)!

(n+1)(n+1)! = [(n+2)-1](n+1)! = (n+2)(n+1)! - (n+1)! = (n+2)! - (n+1)!

=> k=1n   k (k!) + (n+1)(n+1)! = k=1n   k (k!) + (n+2)! - (n+1)!

Form Eqn1.

k=1n   k (k!) + (n+2)! - (n+1)! = (n+1)! - 1 + (n+2)! - (n+1)!

= (n+2)! - 1

Hence proved..

Therefore by mathematical induction, k=1n   k (k!) = (n+1)! -1

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.