Thread: Induction and Recursion

1. Induction and Recursion

Problem :
Prove that for every positive integer n,
1 * 2 * 3 + 2 * 3 * 4 + . . . . . + n(n+1)(n+2) = n(n+1)(n+2)(n+3)/4

Question :
Basis Step:
I want to prove this by determining if P(0) is true which in this case 0(0+1)(0+2)(0+3) = 0 .

Induction Step:
1 * 2 * 3 + 2 * 3 * 4 + . . . . . + k(k+1)(k+2) + (2k+1) =
[k(k+1)(k+2)(k+3)/4 + (2k+1)]

When I simplify I cannot come up with the original solution n(n+1)(n+2)(n+3)/4. I believe I am doing something wrong trying to prove the induction. Any help is appreciated!

2. Originally Posted by Ramin_Shahab
Problem :
Prove that for every positive integer n,
1 * 2 * 3 + 2 * 3 * 4 + . . . . . + n(n+1)(n+2) = n(n+1)(n+2)(n+3)/4

Question :
Basis Step:
I want to prove this by determining if P(0) is true which in this case 0(0+1)(0+2)(0+3) = 0 .

Induction Step:
1 * 2 * 3 + 2 * 3 * 4 + . . . . . + k(k+1)(k+2) + (2k+1) =
[k(k+1)(k+2)(k+3)/4 + (2k+1)]

When I simplify I cannot come up with the original solution n(n+1)(n+2)(n+3)/4. I believe I am doing something wrong trying to prove the induction. Any help is appreciated!
Step 2: Assume true for n = k:

1 * 2 * 3 + 2 * 3 * 4 + . . . . . + k(k+1)(k+2) = k(k+1)(k+2)(k+3)/4

Step 3: Show true for k = n+1.

1 * 2 * 3 + 2 * 3 * 4 + . . . . . + k(k+1)(k+2) + (k+1)(k+2)(k+3) = k(k+1)(k+2)(k+3)/4 + (k+1)(k+2)(k+3)

using step 2.

And it's trivial to show that k(k+1)(k+2)(k+3)/4 + (k+1)(k+2)(k+3) = (k+1)(k+2)(k+3)(k+4)/4 .....