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.

It's an iterated fucntion. https://en.wikipedia.org/wiki/Iterated_function — Martynas, Oct 06 '19 at 09:47

score 1 · Answer 1 · answered Oct 06 '19 at 10:12

1

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

answered Oct 06 '19 at 10:12

Bernard

175,478

isn't the polynomial of degree $2^k$, rather than $2^{k-1}$? – Martynas Oct 06 '19 at 10:20
As I assume that $f^2(x)=(x^2+1)^2+1$ – Martynas Oct 06 '19 at 10:23
It is of degree $2^{k-1} \color{red}{\text{ in }x^2}$ (counting the initial $f(x)$ as the case $k=1$). – Bernard Oct 06 '19 at 10:25
Meaning that $x^2$ to the power of $2^{k-1}$ is simply $2^k$ right? – Martynas Oct 06 '19 at 10:27
Exactly – by the law of exponents. – Bernard Oct 06 '19 at 10:33

José Carlos Santos · Accepted Answer · 2019-10-06T10:48:28.270

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.

edited Oct 06 '19 at 10:48

answered Oct 06 '19 at 10:14

José Carlos Santos

427,504

I have the same question for you. If I assume that $f^2(x)=(x^2+1)^2+1$ then isn't the degree of the $f^k(x)$ simply $2^k$? – Martynas Oct 06 '19 at 10:26
I've edited my answer. I hope that everything is correct now. – José Carlos Santos Oct 06 '19 at 10:30
Another question: why do you start counting from $a_0$ rather than $a_1$? Because if $2^{n-1}+1$ represents the last term of the function, then we ought to count from 1? – Martynas Oct 06 '19 at 10:44
Right. I started counting from $0$; therefore, I should have stopped at $2^n$. I've re-edited my answer. – José Carlos Santos Oct 06 '19 at 10:49

How to prove this property by induction?

2 Answers2