# Creating formula from algorithm

I have this algorithm which i have to convert to polynom of degree 2:

Algorithm is :

input n;
a <- -3;
b <- 5;
for i <- 1 to n do
a <- a+3;
b <- 2*a+b;
done;
output b;


I already figured out that the resulting polynom for $$n>0$$ is :

$$f(n) = 3n^2-3n+5$$

I want to ask if there if this way of figuring out is right under all circunstances:

First let try to write a table for different $$n>0$$

 n | f(n)  | dfn/dn |   (dfn/dn)/dn
1 |  5    |    -     |     -
2 | 11    |    6     |     -
3 | 23    |   12     |     6
4 | 41    |   18     |     6
... ...       ...          ...


It looks that every quadratic polynoms can be expressed in this table so that the last table columns is a Constant Function which is something like second derivative of f(n) isn't it?? I then saw, then function can be written as: $$f(n) = 5 + \sum_{i=1}^{n-1}6i = 5 + 6\ \sum_{i=1}^{n-1}i =3n^2 - 3n + 5$$

which is my final formula.

I want to ask.. is there any trick how to "extract" all coefficients out of table ??

• – lhf Dec 28 '19 at 16:37

For a quadratic $$f(n)=an^2+bn+c$$, you only need three values of the function to determine all coefficients. Since it's a polynomial, you can run your algorithm for any three $$k$$ integers. Let's use $$n=1,2,3$$.

$$f(1) = a + b + c$$ $$f(2) = 4a+2b+c$$ $$f(3) = 9a + 3b+ c$$

While it's straightforward to solve this system directly for $$a,b,c$$, once you have one value the rest are easily calculable using the equations themselves. We'll solve the simpler system:

$$5a+b = f(3)-f(2)$$ $$3a+b=f(2)-f(1)$$

Subtract the equations to find $$a$$ first.

$$a=\dfrac{f(3)-2f(2)+f(1)}{2}$$

Then

$$b = f(2)-f(1)-3a \,\,\,\, \text{ and } \,\,\,\, c = f(1)-a-b$$

Now you have your quadratic and can fill out the entire table.

$$a= \dfrac{23-2(11)+5}{2}=\boxed{\color{red}3}$$ $$b=(11-5-3(\color{red}3)) = \boxed{\color{blue}{-3}}$$ $$c= 5-(\color{red}3)-(\color{blue}{-3})=\boxed{\color{green}5}$$
• I just meant there are better options for the values of $f$, but the loop restricts our choices to $n\ge 1$. If the loop went from $-1$ to $n-2$ the solution here would be "prettier" – David Peterson Dec 30 '19 at 14:25