Can you please explain the third transition in which the sum goes from i=0,4,8 to 4n-4 changes to sum from i=0 to n-1 and 2^i changes to 2^4i?
Is there a closed formula for such transitions?
It can be easily seen by breaking down the sum into its components:
sum( i=0, 4, 8,… ) over 2^i =
2^0 + 2^4 + 2^8 + … + 2^(4n-4) =
2^0 + 2^(4 * 1) + 2^(4 * 2) + … + 2^(4 * (n-1)) =
sum( i=0, 1, 2,… ) over 2^(4 * i).
A similar operation can show the transition for the second summation.
1 Like