Creating formula from algorithm

Question

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 ??

Answer 1

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.

In your case,

$$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}$$

edit: Here is a javascript implementation of the process: https://js.do/daveyp225/386868