v****n
发帖数: 4 | 1 How to calculate the sum of the series:
f(n) = 1 + 2*2 + 3*3 + ... + n*n
but not to use induction method? | t**k
发帖数: 10 | 2 用错位相减法
sum (i-1)i(i+1)
= 0+ 1*2*3 + ... + (i-1)i(i+1) + i(i+1)(i+2) + ... + n(n+1)(n+2)
= 0 + + ... + (i-1)i(i+1) + ... + (n-1)n(n+1) + n(n+1)(n+2)
两式相减得
sum 3i(i+1) = n(n+1)(n+2)
so, sum i(i+1) = n(n+1)(n+2)/3
so, sum i^2 = n(n+1)(n+2)/3 - n(n+1)/2
= n(n+1)(2n+1)/6
【在 v****n 的大作中提到】
: How to calculate the sum of the series:
: f(n) = 1 + 2*2 + 3*3 + ... + n*n
: but not to use induction method?
| t****n
发帖数: 56 | 3 在组合学中，还有种方法，就是：
假如closed form的公式是order为n的多项式，那么其n+1阶的差分为0,其
n阶差分为常数。sum i的通项公式是2阶的：n*(n+1)/2，假设sum i^2是
3阶的，那么可以设其通项公式为a*n^3 + b*n^2 + c*n^1 + d。这样，
就需要4个取值来定a,b,c,d。分别让n=1,2,3,4就可以得到四个方程，解
开这4个方程就可以了。
另外，因为组合数和排列数的代数都是多项式，所以，通常的组合问题都
可以假设有一个多项式存在，问题是对于次数的估计要正确。如果，你对于
该问题认定为通常的组合问题，并且知道次数，那么，至此，问题就解决了。
否则，上面的讨论可以给出一个启发式的估计，然后，你就可以用induction
来证明了.
【在 t**k 的大作中提到】
: 用错位相减法
: sum (i-1)i(i+1)
: = 0+ 1*2*3 + ... + (i-1)i(i+1) + i(i+1)(i+2) + ... + n(n+1)(n+2)
: = 0 + + ... + (i-1)i(i+1) + ... + (n-1)n(n+1) + n(n+1)(n+2)
: 两式相减得
: sum 3i(i+1) = n(n+1)(n+2)
: so, sum i(i+1) = n(n+1)(n+2)/3
: so, sum i^2 = n(n+1)(n+2)/3 - n(n+1)/2
: = n(n+1)(2n+1)/6
| z***e
发帖数: 5600 | 4
Start with (n+1)^3-n^3= 3n^2+3n+1
Sum of above = (N+1)^3 = 3Sum n^2 + 3Sum n+ N+1 (sum from n=0 to N)
and we know what Sum n is...
-Z.
【在 t**k 的大作中提到】
: 用错位相减法
: sum (i-1)i(i+1)
: = 0+ 1*2*3 + ... + (i-1)i(i+1) + i(i+1)(i+2) + ... + n(n+1)(n+2)
: = 0 + + ... + (i-1)i(i+1) + ... + (n-1)n(n+1) + n(n+1)(n+2)
: 两式相减得
: sum 3i(i+1) = n(n+1)(n+2)
: so, sum i(i+1) = n(n+1)(n+2)/3
: so, sum i^2 = n(n+1)(n+2)/3 - n(n+1)/2
: = n(n+1)(2n+1)/6
| w**n
发帖数: 88 | 5 Very nice method , well , there is another way by double counting
since k^2=C(k,1)+2!*C(k,2) (**)
sum(k^2,k=0..n)=sum( C(k,1),k=0..n)+2*sum(C(k,2),k=0..n)
you may know sum(C(k,i),k=0..n)=C(k+1,i+1) //i is a constant
so, answer=C(n+1,2)+2*C(n+1,3)=n*(n+1)*(2*n+1)/6
for k^i case , you can use the same way, but it will take time to figure out
the equation (**)
Anyway ,tandon's method is good for general case , and this method can prove
what he(or she :-) ) said "closed form的公式是order为n的多项式"
【在 t****n 的大作中提到】
: 在组合学中，还有种方法，就是：
: 假如closed form的公式是order为n的多项式，那么其n+1阶的差分为0,其
: n阶差分为常数。sum i的通项公式是2阶的：n*(n+1)/2，假设sum i^2是
: 3阶的，那么可以设其通项公式为a*n^3 + b*n^2 + c*n^1 + d。这样，
: 就需要4个取值来定a,b,c,d。分别让n=1,2,3,4就可以得到四个方程，解
: 开这4个方程就可以了。
: 另外，因为组合数和排列数的代数都是多项式，所以，通常的组合问题都
: 可以假设有一个多项式存在，问题是对于次数的估计要正确。如果，你对于
: 该问题认定为通常的组合问题，并且知道次数，那么，至此，问题就解决了。
: 否则，上面的讨论可以给出一个启发式的估计，然后，你就可以用induction
|
|
