[Solved] Algorithm design manual solution to 1-8

Question

https://cs.stackexchange.com/ is probably better for this. Also I’m pretty sure that $$ formatting only works on some StackExchange sites. But anyways, think about what this algorithm is doing at each step.

We start with p = A_n.

Then we take p = p*x + A_{n-1}. So what is this doing? We now have p = x*A_n + A_{n-1}.

I’ll try one more step. p = p*x + A_{n-2} so now p = (x^2)*A_n + x*A_{n-1} + A{n-2} (here x^2 means x to the power 2, of course).

You should be able to take it from here.

Accepted Answer

https://cs.stackexchange.com/ is probably better for this. Also I’m pretty sure that $$ formatting only works on some StackExchange sites. But anyways, think about what this algorithm is doing at each step.

We start with p = A_n.

Then we take p = p*x + A_{n-1}. So what is this doing? We now have p = x*A_n + A_{n-1}.

I’ll try one more step. p = p*x + A_{n-2} so now p = (x^2)*A_n + x*A_{n-1} + A{n-2} (here x^2 means x to the power 2, of course).

You should be able to take it from here.