Java Reference
In-Depth Information
Example14.4
For our second example of the shifting method, we solve
n
X
i2
i
= 1 2
1
+ 2 2
2
+ 3 2
3
+ + n 2
n
:
f(n) =
i=1
We can achieve our goal if we multiply by two:
n
X
i2
i
= 12
2
+ 22
3
+ 32
4
++ (n1)2
n
+ n2
n+1
:
2f(n) = 2
i=1
The ith term of 2f(n) is i 2
i+1
, while the (i + 1)th term of f(n) is
(i + 1) 2
i+1
. Subtracting one expression from the other yields the sum-
mation of 2
i
and a few non-canceled terms:
n
X
n
X
i2
i
i2
i
2f(n) f(n)
=
2
i=1
i=1
n
n
X
X
i2
i+1
i2
i
:
=
i=1
i=1
Shift i's value in the second summation, substituting (i + 1) for i:
n
X
n
X
= n2
n+1
+
i2
i+1
(i + 1)2
i+1
:
i=0
i=0
Break the second summation into two parts:
n
X
n
X
n
X
= n2
n+1
+
i2
i+1
i2
i+1
2
i+1
:
i=0
i=0
i=0
Cancel like terms:
n
X
= n2
n+1
2
i+1
:
i=0
Again shift i's value in the summation, substituting i for (i + 1):
n
X
= n2
n+1
2
i
:
i=1
Replace the new summation with a solution that we already know:
= n2
n+1
2
n+1
2
:
Finally, reorganize the equation:
=
(n 1)2
n+1
+ 2:
