Induction Proof:

Question

I am stuck on this problem. I understand the fundamentals of induction proofs, but I am unfamiliar with induction on two variables. Here's the prompt:

Prove that for every positive integer $k$, the following is true: For every real number $r > 0$, there are finitely many solutions to $\frac{1}{n_1}+\frac{1}{n_2}+...+ \frac{1}{n_k} = r$. In other words, there exists some number $m$ (that depends on $k$ and $r$ such that there are at most $m$ ways of choosing a positive integer $n_1$, and a (possibly different) positive integer $n_2$, etc., that satisfy the equation.

I have no clue where to start, especially how to reference $m$ in terms of $k$ and $r$. All I know is we cannot induct on $r$ because it is not a natural number.

Answer 1

This is a statement of the form "For all natural numbers $k$ it is the case that...", so this is proved by induction in $k$. Here is the base case:

If $k=1$, then the equation is $\frac{1}{n_1} = r$. If $r$ is an irrational number or $r > 1$, no $n_1$ can be a solution (so $m=0$). If $r$ is rational and $r \leq 1$, we have $r = \frac{x}{y}$, where $x,y \in \mathbb{N}$. If $x$ divides $y$, then there is one solution, else none.

In the inductive step, assume that the statement holds for $k$ and now prove it for $k+1$. I will leave this for you to complete.

Answer 2

Just because multiple variables are involved does not mean that you have to do induction on all those variables: often you just induce over one variable, while you take the other variables as arbitrary (i.e you basically do a universal proof over all the other variables).

Of course, sometimes you don't need to use induction at all, and can do a universal proof for all variables ... or maybe you do induction over 2 out of the 5 variables or ...

In general: for each variable you have a choice of induction or universal proof, though you are right that induction only works for a recursively defined set of objects like the natural numbers.