Induction on functions

Question

I'm working through some homework on induction, and most problems I can solve fine, but I have problem getting started on induction proofs that ask you to prove function relations. For example, here is one problem from my textbook (not homework), that I don't know how to solve:

Suppose a function $f(x)$ has the property that $f(x_1x_2)$ = $f(x_1) + f(x_2)$ for any two positive numbers $x_1$ and $x_2$. Show that $f(x_1x_2···x_n)$ = $f(x_1) + f(x_2) + · · · + f(x_n)$ for the product of any $n$ positive numbers $x_1, x_2, · · · , x_n$.

I can solve problems asking to do 'arithmetic' induction, such as "Prove $n^2 > 4n + 1$ for integers n ≥ 5", but any of these problems relating to functions I can't seem to wrap my head around. What do you differently on these type of problems or how do you do induction on them?

Answer 1

Let $P(n)$ be the following statement:

For any positive numbers $x_1,x_2,\dots,x_n$, $f(x_1x_2\dots x_n)=f(x_1)+f(x_2)+\ldots_+f(x_n)$.

You want to prove that $P(n)$ is true for every positive integer $n$. It’s obvious that $P(1)$ is true, and you’re given that $P(2)$ is true. Suppose that $P(n)$ is true for some integer $n\ge 2$; this is your induction hypothesis. You want to use it to prove that $P(n+1)$ is true, so suppose that $x_1,\dots,x_{n+1}$ are positive numbers. Let $y=x_1x_2\dots x_n$, the product of the first $n$ of these numbers. Then

$$\begin{align*} f(x_1x_2\dots x_nx_{n+1})&=f(yx_{n+1})\\ &=f(y)+f(x_{n+1})\\ &\overset{(*)}=\Big(f(x_1)+f(x_2)+\ldots+f(x_n)\Big)+f(x_{n+1})\\ &=f(x_1)+f(x_2)+\ldots+f(x_n)+f(x_{n+1})\;, \end{align*}$$

which is exactly what $P(n+1)$ says. The starred step is where I used the induction hypothesis; the previous step just used the original hypothesis that $P(2)$ is true.

This shows that $P(n)$ does imply $P(n+1)$, and the principle of mathematical induction now lets us conclude that $P(n)$ is true for all $n\in\Bbb Z^+$.

Answer 2

One difference is that in the first problem, you are using induction on syntax (here, the number of plus signs.) The way you would do the induction step in this particular problem is to notice that $$f(x_1x_2 \cdots x_{n+1}) = f((x_1x_2 \cdots x_n) \cdot x_{n+1}) = f(x_1x_2 \cdots x_n) + f(x_{n+1}) = (f(x_1) + f(x_2) + \cdots + f(x_n)) + f(x_{n+1}).$$ (You could turn it into an ordinary induction by writing the summation with $\Sigma$-notation, I suppose.)

Answer 3

You usually have to invoke properties of functions or conditions that they give you. For instance with this problem a hint would be $f(x_1,x_2,x_3)=f(x_1,x_2)+f(x_3)$. Or in general $f(x_1,..,x_n)= f(x_1,x_2,...,x_n-1)+f(x_n)$.

The first time you declared the function the input was separated by a comma but the second time they were not. I'm assumming you ommited the comma by accident.