# Proof by Induction

1. Sep 15, 2012

### Tsunoyukami

I'm having a little bit of difficulty with proofs by induction. I believe I understand the principles behind induction but find that I often get "stuck" in my proof - and I can "see" that its true but am not sure how to get that one step that will finish the proof.

When using mathematical induction to show that a statement is true we first show that it is true for the lowest value (usually 0 or 1) and then assume it holds true for some value k > 0 (or 1). Then we show that if the statement is true for the value (k+1) that it is true for all values, correct?

So here is a question I must complete for homework from Stephen D. Fisher's Complex Variables, 2e:

"12. Let $z_1, z_2, ..., z_n$ be complex numbers. Establish the following formulas by mathematical induction:

a) $|z_1 z_2 ... z_n| = |z_1| |z_2| ... |z_n|$" (Section 1.1, page 9).

Here is my attempt at a solution:

First we show that this statement is true for n = 1 (which is obvious) - we find:

$|z_1| = |z_1|$

Next we assume that this statement holds true for some k > 1; that is that the following is true:

$|z_1 z_2 ... z_k| = |z_1| |z_2| ... |z_k|$

Lastly we must show that for some value, (k+1), the statement $|z_1 z_2 ... z_n| = |z_1| |z_2| ... |z_n|$ is true. So:

$|z_1 z_2 ... z_k z_{k+1}| = |z_1| |z_2| ... |z_k| |z_{k+1}| (1)$

To me this seems obvious is I can write:

$|z_1 z_2 ... z_k z_{k+1}| = |z_1 z_2 ... z_k| |z_{k+1}| (2)$
$|z_1 z_2 ... z_k| |z_{k+1}| = |z_1| |z_2| ... |z_k| |z_{k+1}| (3)$

By using the assumption that it holds true for k > 1. Is this a valid step to make? Can I go from (1) to (2), from which point (3) readily follows? Or am I missing something?

Any assistance is much appreciated; please provide me confirmation or a hint to lead me in the right direction - thanks!

2. Sep 15, 2012

### Curious3141

You need to prove that $|z_1z_2| = |z_1||z_2|$ then apply the inductive hypothesis.

3. Sep 15, 2012

### LCKurtz

You should start with n = 2. I will explain why below.
No, we don't show it is true for "some value". We show that if it is true for $n=k$ it is true the next value, which is $k+1$
That assumes you know it works for 2 complex numbers, which you haven't proven.

That you can go from step 2 to step 3 is because your induction hypothesis is that it works for $n=k$. But notice that this argument doesn't work for $k=2$. That is why you need to start with $k=2$.

There is a common example to illustrate the fallacy your argument falls into.

Theorem. If one man in a group of n men is a millionaire, they all are millionaires.

Proof: n=1 Obvious
Assume it is true for n = k, that is, if one man in a group of k men is a millionaire, they all are.

Now suppose you have a group of k+1 men, and one of them is a millionaire. Divide them into two groups, one containing k men and the other 1 man, with the millionaire in the larger group. By the induction hypothesis, 1 man in the group of k men is a millionaire so all k of that group are. Now take 1 of the millionaires out of the larger group and exchange him with the lone man. Now by the same argument, the man who was the lone man is also a millionaire, so everyone is.

Last edited: Sep 15, 2012
4. Sep 15, 2012

### Tsunoyukami

Okay...so using $z_1 = x_1 + iy_1$ and $z_2 = x_2 + iy_2$:

$|z_1 z_2| = |(x_1 + iy_1)(x_2 +iy_2)| = |(x_1 x_2 - y_1 y_2) + i(x_1 y_2 + x_2 y_1)|$

Now using definition of $|z|$ is such that $|z| = |x + iy| = \sqrt{x^2 + y^2}$ we find:

$|z_1 z_2| = |(x_1 x_2 - y_1 y_2) + i(x_1 y_2 + x_2 y_1)| = \sqrt{(x_1 x_2 - y_1 y_2)^2 + (x_1 y_2 + x_2 y_1)^2}$

Which, when simplified, yields:

$|z_1 z_2| = \sqrt{x_1 ^2 x_2 ^2 + x_1^2 y_2^2 + x_2^2 y_1^2 +y_1^2 y_2^2}$

Which can easily be shown to be equal to $|z_1||z_2|$.

So now that I have shown that $|z_1 z_2| = |z_1| |z_2|$ I can assume that the given statement holds true for a specific value of n such that n = k and I can move from step (2) to step (3) because I have proven the statement for k =2, correct?

5. Sep 15, 2012

Yes.