How to prove this property by induction?

Question

Assume we have a function $f(x)=x^2+1$ and I iterate the function so that $f^n(x)=(f^{n-1})^2 +1$. I was able to generalize that the number of terms $n$ after some number $k$ iterations is $n=\frac{2^k+2}{2}$

I need to prove this somehow, and I think mathematical induction is the way to go. I found the base case and the $P_k$ case. However, I am not sure how to approach $P_{k+1}$ and find an expression that would clearly show that this property is true.

Answer 1

For each $n\in\mathbb N$, $f^n(x)$ is a polynomial of the form$$a_0+a_1x^2+a_2x^4+\cdots+a_{2^{n-1}}x^{2^n},$$with each $a_k$ greater than $0$. This is clearly true if $n=1$. If this is true for a certain $n$, then$$f^{n+1}(x)=(a_0+a_1x^2+a_2x^4+\cdots+a_{2^{n-1}}x^{2^n})^2+1,$$which is of the form$$b_0+b_1x^2+a_2x^4+\cdots+b_{2^n}x^{2^{n+1}},$$with each $b_k$ greater than $0$.

In particular, $f^n(x)$ has $2^{n-1}+1$ terms.

Answer 2

Hint: You can show by induction that $f^k(x) $ is a monic polynomial in $x^2$ of degree $2^{k-1}$ and that it does have all terms of degree $<2^{k-1}$.

Now a general polynomial of degree d requires $d+1$ coefficients. Note that $\frac{2^k+2}2=2^{k-1}+1$.