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