Finding $f(x)$ when given a composite function?

Question

CONTEXT: Uni homework question made up by lecturer

If, for $n=0$, $1$, $2$, $\ldots$ you're given $f_0(x)=\frac{1}{2-x}$ and $f_{n+1}=f_0(f_n(x))$, how do you prove that your formula for $f_n(x)$ is correct by mathematical induction?

UPDATE

I have computed the first few terms:

$f_1(x)=\frac{2-x}{3-2x}$

$f_2(x)=\frac{3-2x}{4-3x}$

$f_3(x)=\frac{4-3x}{5-4x}$

$f_4(x)=\frac{5-4x}{6-5x}$

Then, from observation of these I developed:

$f_n(x)=\frac{n+1-nx}{n+2-(n+1)x}$

But I don't see how you're supposed to prove this with mathematical induction as it has variable $x$ in it as well as the $n$.

Answer 1

You have already shown the base case for your induction. Suppose that your proposition

$$f_n(x) = \frac{n+1-nx}{n+2-(n+1)x}, $$

holds for $n=N$. We must show that the result also holds for $n=N+1$. Following the formula you were given for computing $f_{N+1}(x)$ we have,

$$ f_{N+1}(x) = f_0(f_N(x)) = f_0 \left( \frac{N+1-Nx}{N+2-(N+1)x} \right),$$

where we have used the inductive assumption to substitute $f_N(x)$. Now we apply $f_0$,

$$ f_{N+1}(x) = \frac{1}{2-\frac{N+1-Nx}{N+2-(N+1)x}}. $$

We now simplify this expression,

$$f_{N+1}(x) = \frac{N+2-(N+1)x}{2(N+2-(N+1)x) - (N+1 - Nx)} $$

and collect together all of the like terms

$$f_{N+1}(x) = \frac{(N+1) + 1 - (N+1)x}{((N+1) + 2) - ((N+1) + 1)x}.$$

This completes the inductive argument.

Answer 2

Said in very broad terms, induction is the process of solving some problem for all values of $n$ when you can solve it for some $n_0$ and can derive the solution of the problem $n+1$ knowing the solution for $n$.

In your case, the problem is to "find the symbolic expression of $f_n(x)$", which you managed perfectly.

---

$$f_0(x)=\frac{n+1-nx}{(n+2)-(n+1)x}=\frac{1}{2-x}$$ is true.

And

$$f_n(x)=\frac{n+1-nx}{(n+2)-(n+1)x}\implies f_{n+1}(x)=f_0(f_n(x))=\frac{n+2-(n+1)x}{(n+3)-(n+2)x}$$ is true as well, as is shown by reworking the expressions.

Answer 3

Just calculate $f_{n+1}$ from $f_{n}$, with both depending on x and check if the pattern holds. The variable x is irrelevant in this case, as you perform your induction on n.

Or, if you prefer it in these words for better understanding, the "pattern" has to still be true for every value of x

Answer 4

I think you have not been taught what induction (along the naturals) really is. Induction should always be understood as a rule that can be applied to any property $Q$ on $\mathbb{N}$. When we say that $Q$ is a property on $\mathbb{N}$ we mean that $Q(k)$ is a statement about $k$ for any $k ∈ \mathbb{N}$. Note that if $Q$ is defined in any context where we have other objects, $Q$ can also depend on those other objects.

In your case, you should be given (the quantifiers are erroneously missing from the question):

  $f_0(x)=1/(2−x)$ and $f_{n+1} = f_0(f_n(x))$ for every $n ∈ \mathbb{N}$ and $x ∈ \mathbb{R} ∖ {2}$.

And in this context you want to prove:

  $f_n(x) = (n+1−nx)/(n+2−(n+1)x)$ for every $n ∈ \mathbb{N}$ and $x ∈ \mathbb{R} ∖ {2}$.

It suffices to do the following:

  Given any $x ∈ \mathbb{R} ∖ {2}$:

    [In this context you have $x$.]

    Define $Q(n)$ to assert that $f_n(x) = (n+1−nx)/(n+2−(n+1)x)$, for each $n ∈ \mathbb{N}$.

    Then $Q(0)$ is true because ...

    Given any $n ∈ \mathbb{N}$ such that $Q(n)$ is true:

      ...

      Thus $Q(n+1)$ is true.

    Therefore by induction $f_n(x) = (n+1−nx)/(n+2−(n+1)x)$ for every $n ∈ \mathbb{N}$.

Answer 5

In fact having $f_n(x)$ in hand, we need to prove that $$f_{n+1}(x)=\frac{n+2-(n+1)x}{n+3-(n+2)x}$$while this is easy since $$f_{n+1}(x){=f_0(f_n(x))\\=f_0\left(\frac{n+1-nx}{n+2-(n+1)x}\right)\\={1\over 2-\frac{n+1-nx}{n+2-(n+1)x}}\\={1\over {2n+4-2nx-2x-n-1+nx\over n+2-(n+1)x}}\\={1\over {n+3-nx-2x\over n+2-(n+1)x}}\\=\frac{n+2-(n+1)x}{n+3-(n+2)x}}$$and the proof is complete $\blacksquare$