# Is my induction statement correct ? (proof correctness)

I have a problem with coming up with a statement for this proof:

The following algorithm takes x, $a_i, 0 ≤ i ≤ n$, as input and returns $\displaystyle\sum_{j=0}^n a_jx^j$ as output

Input: x, a_i, 0 ≤ i ≤ n;

Output: y;

begin
1.y := 0;
2.for i := n step −1 downto 0 do
3.y := $a_i$ + x ∗ y;
end.


This is what I have right now: (not sure if correct):

for 0 to k and at the kth iteration where line is at number 3, y is the output of the summation of $a_i$ (i from zero to n) plus x multiplied by y.

• Could you please format your last sentence into (pseudo)code? It's really hard to get my head around that as of now. Also, is $a_i$ a sequence or a constant? Feb 6, 2017 at 23:40
• @theSongbird, nothing is said about $a_i$ but I think it is an array of different inputs, also, updated the code and statement Feb 7, 2017 at 0:03

I guess that by "for 0 to k and at the kth iteration where line is at number 3, y is the output of the summation of $a_i$ (i from zero to n) plus x multiplied by y" you mean:

1. y := 0;
2. for i:= 0 to k do
3.   y := a_i + x*y;


If this is the case, then it's correct. Seeing that you're unsure about it, I'll try to explain it:

In line 2 you're telling the program/ machine/ man to run the given code block a given number of times.

In line 3 the right-hand side calculates the given expression using the old value of y. After this it overwrites y, giving it it's new value. When you'll be running the actual code, the compiler will know to calculate the right-hand side as previously mentioned before asserting it to the left-hand side.

Hope that helped!