Alternate expression for finite summation

90 Views Asked by At

"How many arithmetic operations are required to directly compute $$y=1+x+x^2+...+x^{1023}$$ Use a formula for the sum to come up with an alternate expression for $y$, and show that only 10 multiplications are now required."

Workings so far: I determined that the number of multiplications would be 1024 (using nested evaluations) and that the number of additions would also be 1024. I re-wrote $y$ as $$y=\sum_{n=0}^{1023}{x^n}$$ But I do not understand how to show that only 10 multiplications are required.

Any help or insight would be greatly appreciated. Thanks in advance!

1

There are 1 best solutions below

1
On BEST ANSWER

Hint $1$: Multiply your sum with $1-x$, and see what happens. :-)

Hint $2$: $1024=2^{10}$, $a^b\cdot a^c=a^{b+c}$, and $2^n+2^n=2\cdot2^n=2^{n+1}$.