• Support PF! Buy your school textbooks, materials and every day products Here!

Proof by Induction

  • #1
215
11
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!
 

Answers and Replies

  • #2
Curious3141
Homework Helper
2,843
87
You need to prove that [itex]|z_1z_2| = |z_1||z_2|[/itex] then apply the inductive hypothesis.
 
  • #3
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,535
751
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|##
You should start with n = 2. I will explain why below.
Next we assume that this statement holds true for some k > 2; 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.
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##
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)##
That assumes you know it works for 2 complex numbers, which you haven't proven.

##|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!
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:
  • #4
215
11
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
Curious3141
Homework Helper
2,843
87
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?
Yes.
 

Related Threads on Proof by Induction

  • Last Post
Replies
6
Views
748
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
891
  • Last Post
Replies
2
Views
606
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
3
Views
874
Top