How do you solve this using mathematical induction. Prove that: 1*N+2(n-1)+3(n-2)+...+(n-1)*2+n*1=(1/6)n(n+1)(n+2)?

2014-12-21 8:50 pm

回答 (4)

2014-12-21 9:12 pm
You want to show 1*n + 2(n-1) + 3(n-2) + ...+ (n-1)(n - (n-1)) = n(n+1)(n+2)/6.

Clearly it works for n = 1.

By induction assume 1*n + 2(n-1) + 3(n-2) + ...+ (n-1)(n - (n-1)) = n(n+1)(n+2)/6. We want to show 1*(n+1) + 2(n+1-1) + 3(n+1-2) + ...+ (n+1-1)(n+1 - (n+1-1)) = (n+1)(n+2)(n+3)/6.

Argue as follows:
1*(n+1) + 2(n+1-1) + 3(n+1-2) + ...+ (n+1-1)(n+1 - (n+1 -1)) (taking the extra 1 out of the parentheses)
= {1*n + 2(n-1) + 3(n-2) + ...+ (n-1)(n - (n-1))} + 1*1 + 2*1 + 3*1 + ...+ (n +1)*1 =
=n(n+1)(n+2)/6 + (n+1)(n+2)/2
=(n+1)(n+2){n/6 + 1/2)
=(n+1)(n+2)(n+3)/6

And we're done.
2014-12-22 12:01 am
To solve by induction, assume it is true for n=k
then evaluate at n=k+1 and take the difference.
You see the difference is 1+2+3+...+k+k+1 (note one term has been added)
show that this sum is the same as the difference between
1/6(k*(k+1)*(K+2)) and 1/6((k+1)(k+2)(k+3))
= 1/6(k+1)(k+2)*3=(k+1)(K+2)/2
2014-12-21 10:21 pm
Since you already have an induction answer here is a quick way:

∑ x(N-x+1) = (N+1)∑x - ∑x²

for x=1..N

∑ x = (1/2)N(N+1)
∑ x² = (1/6)N(N+1)(2N+1)

∑ x(N-x+1) = N(N+1)[(N+1)/2 - (2N+1)/6]
= N(N+1)[3N+3 - 2N-1]/6
= N(N+1)(N+2)/6

Assuming, of course, that you accept the closed forms of ∑ x and ∑ x²
2014-12-21 9:27 pm
Prove that sum x = 1 to n of [x * (n-x)] = what???

I'll assume you're looking for (n^3 + 3n^2 + 2n)/6.
(Another possibility is sum x=1 to n of [sum y=1 to x of [y]], but that's much harder! )

First, the trivial case: Prove that it's true for n = 1. That's pretty easy. There's only one term in the sum, 1, and that equals (1^3 + 3*1^2 + 2*1)/6; Done.

To prove the inductive case, assume that
sum x = 1 to n of [x * (n-x)] = (n^3 + 3n^2 + 2n)/6
and try to prove that
sum x = 1 to n+1 of [x * (n+1-x)] = ((n+1)^3 + 3(n+1)^2 + 2(n+1))/6

By pulling off the last term we know that
sum x = 1 to n+1 of [x * (n+1-x)]
= (n+1) + sum x = 1 to n of [x * (n+1-x)]
Rearranging a little:
= (n+1) + sum x = 1 to n of [x + x * (n-x)]
= (n+1) + sum x = 1 to n of [x] + sum x = 1 to n of [x * (n-x)]

Now use the lemma that :
sum x = 1 to n of [x] = (n^2 + n)/2.
We can prove this later.

= (n+1) + (n^2 + n)/2 + sum x = 1 to n of [x * (n-x)]
Now use the inductive assumption to evaluate the sum that's left.
= (n+1) + (n^2 + n)/2 + (n^3 + 3n^2 + 2n)/6

We only have to show that this is equal to
((n+1)^3 + 3(n+1)^2 + 2(n+1))/6.
or,
(n^3 + 3n^2 + 3n + 1 + 3n^2 + 6n + 3 + 2n + 2)/6
(n^3 + 6n^2 + 11n + 6)/6

Here goes:
(n+1) + (n^2 + n)/2 + (n^3 + 3n^2 + 2n)/6
= [6(n+1) + 3(n^2 + n) + (n^3 + 3n^2 + 2n)]/6
= [6n + 6 + 3n^2 + 3n + n^3 + 3n^2 + 2n] /6
= [n^3 + 6n^2 + 11n +6] /6

And we're done.

Well, except for the "lemma" I used.
sum x = 1 to n of [x] = (n^2 + n)/2.

This can also be proved by induction. Show that it's true for n=1:
1 = (1^2 + 1)/2. Easy.

Then assume that sum x = 1 to n of [x] = (n^2 + n)/2
and show that sum x = 1 to n+1 of [x] = ((n+1)^2 + (n+1))/2.
sum x = 1 to n+1 of [x]
= (n+1) + sum x = 1 to n of [x]
= (n+1) + (n^2 + n)/2
= (n^2 + n + 2n + 2)/2
= (n^2 + 2n + 1 + n + 1)/2
= ((n+1)^2 + (n+1))/2.


收錄日期: 2021-04-21 00:55:48
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20141221125039AAVNECV

檢視 Wayback Machine 備份