AoPS Academy
and 
not is a perfect square for all 
.
![$\color[rgb]{0.35,0.35,0.35}g_1(x) = f(x)$](http://latex.artofproblemsolving.com/4/8/1/48141a7d9da383028cdede6d8a84d5b294668763.png)
![$\color[rgb]{0.35,0.35,0.35}g_{k + 1}(x) = f(g_k(x))$](http://latex.artofproblemsolving.com/6/1/c/61cf758619c8bc1261fcf939e6170cdfecb2a5a0.png)
![$\color[rgb]{0.35,0.35,0.35}r_k$](http://latex.artofproblemsolving.com/b/a/b/bab0b3167e07a9d4a7784160bf6708d3c01662a7.png)
is the average of the roots of ![$\color[rgb]{0.35,0.35,0.35}g_k$](http://latex.artofproblemsolving.com/c/7/2/c72222930a9c1fbed785adce23e8e75da00e9f9f.png)
and ![$\color[rgb]{0.35,0.35,0.35}g_{2}(x) = f(g_1(x))$](http://latex.artofproblemsolving.com/6/c/4/6c49ebc1440afa5e849cc69c2612ee49d71ee414.png)
.. but wait, ..![$\color[rgb]{0.35,0.35,0.35}g_{2}(x) = f(f(x))$](http://latex.artofproblemsolving.com/6/3/b/63b75b66d45768b4cb78937b308a912c04c84954.png)
.. and looking at![$\color[rgb]{0.35,0.35,0.35}g_{3}(x) = f(g_2(x))$](http://latex.artofproblemsolving.com/b/f/7/bf72a4c8ac6e5e65e230996cfef523b4608c69eb.png)
, we can see that there is a pattern to![$\color[rgb]{0.35,0.35,0.35}g_n(x)$](http://latex.artofproblemsolving.com/2/3/e/23e5989d6d800eedaab94a9c93dd1f17cf54cc70.png)
= the repeated composition of f(x) n times.![$\color[rgb]{0.35,0.35,0.35}g_{19}(x) = f(f(f....(x)))))))))))))))))))$](http://latex.artofproblemsolving.com/5/7/7/577d10e893e0433e3ea569c74ca1636c95088fa6.png)
, where the ... represents the continuation of the 19 f's. This simplifies our problem some.![\[\color[rgb]{0.35,0.35,0.35} f(x) = a_n x^n + a_{n - 1} x^{n - 1} + \dots + a_1 x + a_0 \]](http://latex.artofproblemsolving.com/e/7/7/e7764f9dce30626688355505bb7d1a1690da43c1.png)
If we perform![\[g_2\]](http://latex.artofproblemsolving.com/d/0/6/d06075067e244737163dcb0d46e28f9575228ece.png)
, we get![\[a_n (a_n x^n + a_{n - 1} x^{n - 1} + \dots + a_1 x + a_0)^n + a_{n - 1} (a_n x^n + a_{n - 1} x^{n - 1} + \dots + a_1 x + a_0)^{n - 1} + \dots + a_1 (a_n x^n + a_{n - 1} x^{n - 1} + \dots + a_1 x + a_0) + a_0\]](http://latex.artofproblemsolving.com/8/f/9/8f9ac844a7d0d828551679243654143394821b24.png)
![\[a_n x^n + a_{n - 1} a^{n - 1} + \dots + a_1 x + a_0\]](http://latex.artofproblemsolving.com/0/a/f/0af52c4aded6ed896993719c612612af4a1f2c32.png)
, the sum is![\[\frac{-(a_{n-1})}{a_n}\]](http://latex.artofproblemsolving.com/0/9/0/090aac52cec79ea6ef7bf5cabb4e16d57b0c9459.png)
.. However, when the composition occurs, how will the sum change?![\[((x-1)(x-1))^2\]](http://latex.artofproblemsolving.com/d/d/5/dd5af9f53cfb87ddd4e5d1e121831c1f23c28a48.png)
= (x-1)(x-1)(x-1)(x-1) .. so it adds on another sets. So for whatever sum is there originally, gets multiplied by n, where n is the degree of the polynomial.![\[g_n(x)\]](http://latex.artofproblemsolving.com/1/5/0/1509a2ea1f6874eb20e35a4a572d17ac12f1f10e.png)
=![\[\frac{-(a_{n-1}(n))}{a_n}\]](http://latex.artofproblemsolving.com/1/8/b/18ba211c6a1984f319c0122c6df3866b998b7888.png)
that means the average of the roots is simply![\[\frac{\frac{-(a_{n-1}(n))}{a_n}}{n^n}\]](http://latex.artofproblemsolving.com/5/3/7/537cefab8bb997999e59a8aedd840d45247e8156.png)
, which simplifies to:![\[r_n\]](http://latex.artofproblemsolving.com/b/5/b/b5b9a2c03e4dc2a98f75a8ee544b53699d92bf77.png)
=![\[\frac{\frac{-(a_{n-1})}{a_n}}{n^(n-1)}\]](http://latex.artofproblemsolving.com/0/6/a/06a93b7682ed49c50b204eca930135b8012059b7.png)
..=, to see how repeated composition of a single function affects the average of the roots.![\[q(x)\]](http://latex.artofproblemsolving.com/8/e/2/8e20b6e10b6bdbecdae6d59d6ed7cf3ab14d70d8.png)
=![\[x^2 - 6x + 5\]](http://latex.artofproblemsolving.com/a/8/1/a81b60e2c4bfa16d1a69fdc9c7f1020baa0a011d.png)
..![\[q_2(x)\]](http://latex.artofproblemsolving.com/b/3/0/b302c9743a07e34e7f5caa02d8dc727f85ffcc6f.png)
, and only taking in account the x^2, we get![\[(x^2 - 6x + 5)^2\]](http://latex.artofproblemsolving.com/8/b/f/8bf63e74e4c69e763868645332b2d0edc7890b05.png)
.. multiplying this out, and taking only in account the x^4 and x^3 terms, we get![\[x^4 - 12x^3 ..\]](http://latex.artofproblemsolving.com/2/a/6/2a60c98ebdd1a6eacaf2f3a130cf15f436612289.png)
.. we see that the sum of the roots of this is 12, but since there were originally 2 roots, and we squared this polynomial when performing composition, we got 4 roots instead since by the fundamental theorem of algebra a polynomial with nth degree has n roots.=we can verify that the average of the roots will stay the same despite repeated composition. is the same for all values of k.![$\color[rgb]{0.35,0.35,0.35}r_{19}$](http://latex.artofproblemsolving.com/b/e/b/bebc74e9a0059877796c9487e33710c3cb55f6bc.png)
= ![$\color[rgb]{0.35,0.35,0.35}r_{89}$](http://latex.artofproblemsolving.com/e/8/6/e86c4918d7887213005f4d7b48739c7cebec443a.png)
= 89
![$\color[rgb]{0.35,0.35,0.35}v_1=2$](http://latex.artofproblemsolving.com/2/0/4/204b13717fb1dec258e4917232ca9c96344031d2.png)
, ![$\color[rgb]{0.35,0.35,0.35}v_2=4$](http://latex.artofproblemsolving.com/b/c/2/bc24e9589aaf75cb848e9fddeef43fb7a6fea2c3.png)
and ![$\color[rgb]{0.35,0.35,0.35} v_{n+1}=3v_n-v_{n-1}$](http://latex.artofproblemsolving.com/8/7/3/8734d09c683e906771abf049d89b273196175585.png)
, prove that ![$\color[rgb]{0.35,0.35,0.35}v_n=2F_{2n-1}$](http://latex.artofproblemsolving.com/b/1/e/b1efbac9eef93c5649dab70be54ae2286ca5b2f0.png)
, where the terms ![$\color[rgb]{0.35,0.35,0.35}F_n$](http://latex.artofproblemsolving.com/0/2/5/025c95f57f5317da3d9739c1620448d8f7cf4e47.png)
are the Fibonacci numbers.
Prove that
,