Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,382
But then i will have to work harder. Then again, I am not a scab (I do not cross picket lines)
mathematical induction proof problem
- Thread starter allegansveritatem
- Start date
Harry_the_cat
Elite Member
- Joined
- Mar 16, 2016
- Messages
- 3,693
That's Subhotosh's job.
pka
Elite Member
- Joined
- Jan 29, 2005
- Messages
- 11,971
When \(n=1\) the number \(10^2+3\cdot 10^1+5=135=9\cdot 15\). True for \(n=1\).
Now suppose that \(\exists J\in \mathbb{Z}^+\) such that \(10^{K+1}+3\cdot 10^K+5=9\cdot J\)
Now consider:
\(\begin{gathered}
\quad {10^{(K + 1) + 1}} + 3 \cdot {10^{K + 1}} + 5 \hfill \\
= \left\{ {({{10}^{K + 1}} + 3 \cdot {{10}^K} + 5)10} \right\} - 45 \hfill \\
= 10\left( {9J} \right) - 45 \hfill \\
= 9(10J-5 )\hfill \\
\end{gathered} \)
DONE.
Great comments. In addition
First, I like to keep separate the general number n and the arbitrary number k
and start by writing down the general proposition to be proved
[MATH]\text {P}(n) \text { is } n \in Z_{>0} \implies 9 \ | \ 10^{(n+1)} + 3 \cdot 10^n + 5.[/MATH]
As a practical matter, I may well play around with the proposition for some small numbers just to see if that experimentation teaches me something before I throw myself into a proof. In any case, it will give me the base case for induction.
[MATH]10^{(1+1)} + 3 * 10^1 +5 = 100 + 30 + 5 = 135 = 9 * 15 \implies P(1) \text { is true.}[/MATH]
Second, I hate the traditional vocabulary used for mathematical induction. The second step is usually described as the induction "hypothesis." That interfered with my intuition. There is nothing hypothetical about the following statement because we JUST PROVED IT.
[MATH]\text {There exists at least one positive integer for which P is true.}[/MATH]
[MATH]\text {Let } k \text { be an arbitrary one of those numbers.}[/MATH]
Third, I agree wholeheartedly with writing down what the consequences are of the preceding statement. It means you do not need to burden your memory with those consequences, and it forces you to articulate them consciously.
[MATH]k \in \mathbb Z_{>0} \implies k + 1 \in \mathbb Z_{>0}[/MATH].
[MATH]\text {P}(k) \text { is true} \implies \exists \text { an integer } j \ge 1 \text { such that }\\ 9j = 10^{(k+1)} + 3 \cdot 10^k + 5.[/MATH]Fourth, we want to try to express the expression of interest with respect to k + 1 in terms of WHAT WE KNOW ABOUT k.
[MATH]10^{\{(k+1)+1\}} + 3 \cdot 10^{(k+1)} + 5 =10(10^{(k+1)} + 3^10^k) + 5.[/MATH]
The expression in parentheses on the RHS looks a great deal like what we know about k. How do we get a 5 in there. We remember that
a - a = 0.
[MATH]10(10^{(k+1)} + 310^k) + 5 = 10(10^{(k+1)} + 3^10^k) + 50 - 50 + 5 = \\ 10(10^{(k+1)} + 3^10^k + 5) - 45 = 10 * 9j - 45 = 9(10j - 5).[/MATH][MATH]\therefore 9 \ | \ 10^{\{(k+1)+1\}} + 3 \cdot 10^{(k+1)} + 5 \implies P(k+1) \text { is true.}[/MATH]
[MATH]\therefore P(n) \text { is true for all positive integers. Q.E.D.}[/MATH]
There probably are other ways to do a proof by induction, but that way of proceeding has usually worked for me.
First, I like to keep separate the general number n and the arbitrary number k
and start by writing down the general proposition to be proved
[MATH]\text {P}(n) \text { is } n \in Z_{>0} \implies 9 \ | \ 10^{(n+1)} + 3 \cdot 10^n + 5.[/MATH]
As a practical matter, I may well play around with the proposition for some small numbers just to see if that experimentation teaches me something before I throw myself into a proof. In any case, it will give me the base case for induction.
[MATH]10^{(1+1)} + 3 * 10^1 +5 = 100 + 30 + 5 = 135 = 9 * 15 \implies P(1) \text { is true.}[/MATH]
Second, I hate the traditional vocabulary used for mathematical induction. The second step is usually described as the induction "hypothesis." That interfered with my intuition. There is nothing hypothetical about the following statement because we JUST PROVED IT.
[MATH]\text {There exists at least one positive integer for which P is true.}[/MATH]
[MATH]\text {Let } k \text { be an arbitrary one of those numbers.}[/MATH]
Third, I agree wholeheartedly with writing down what the consequences are of the preceding statement. It means you do not need to burden your memory with those consequences, and it forces you to articulate them consciously.
[MATH]k \in \mathbb Z_{>0} \implies k + 1 \in \mathbb Z_{>0}[/MATH].
[MATH]\text {P}(k) \text { is true} \implies \exists \text { an integer } j \ge 1 \text { such that }\\ 9j = 10^{(k+1)} + 3 \cdot 10^k + 5.[/MATH]Fourth, we want to try to express the expression of interest with respect to k + 1 in terms of WHAT WE KNOW ABOUT k.
[MATH]10^{\{(k+1)+1\}} + 3 \cdot 10^{(k+1)} + 5 =10(10^{(k+1)} + 3^10^k) + 5.[/MATH]
The expression in parentheses on the RHS looks a great deal like what we know about k. How do we get a 5 in there. We remember that
a - a = 0.
[MATH]10(10^{(k+1)} + 310^k) + 5 = 10(10^{(k+1)} + 3^10^k) + 50 - 50 + 5 = \\ 10(10^{(k+1)} + 3^10^k + 5) - 45 = 10 * 9j - 45 = 9(10j - 5).[/MATH][MATH]\therefore 9 \ | \ 10^{\{(k+1)+1\}} + 3 \cdot 10^{(k+1)} + 5 \implies P(k+1) \text { is true.}[/MATH]
[MATH]\therefore P(n) \text { is true for all positive integers. Q.E.D.}[/MATH]
There probably are other ways to do a proof by induction, but that way of proceeding has usually worked for me.
Last edited:
Harry_the_cat
Elite Member
- Joined
- Mar 16, 2016
- Messages
- 3,693
I thought I would also add an alternative. As an ex-secondary teacher, I use less of the formal mathematical notation.
To prove: \(\displaystyle P(n): 10^{n+1} + 3 * 10^n +5 \) is divisible by \(\displaystyle 9\) for all positive integers \(\displaystyle n\).
PROOF BY INDUCTION:
Step 1
Prove true for \(\displaystyle n=1\)
\(\displaystyle P(1): 10^{(1+1)} + 3 * 10^1 + 5 =100 + 30 + 5 =135 = 9 * 15\) which is clearly a multiple of \(\displaystyle 9\)
Therefore \(\displaystyle P(1) \) is true.
Step 2
Assume true for \(\displaystyle n=k\)
ie \(\displaystyle P(k): 10^{k+1} + 3 * 10^k + 5\) is divisible by \(\displaystyle 9\)
ie \(\displaystyle 10^{k+1} + 3 * 10^k + 5 = 9m\) for some integer \(\displaystyle m\)
Step 3
Prove \(\displaystyle P(k+1): 10^{(k+1)+1} + 3 * 10^{k+1} +5\) is divisible by \(\displaystyle 9\)
Proof:
\(\displaystyle 10^{(k+1)+1} + 3 * 10^{k+1} + 5\)
\(\displaystyle =10^{k+2} + 3 * 10^{k+1} + 5\)
\(\displaystyle = 10 * 10^{k+1} + 3 * 10 * 10^k +5\)
\(\displaystyle =10(10^{k+1} + 3 * 10^k) +5\)
\(\displaystyle =(9+1)(10^{k+1} + 3 * 10^k) +5\)
\(\displaystyle =9(10^{k+1} + 3 * 10^k) +1(10^{k+1} + 3 * 10^k) +5\)
\(\displaystyle =9(10^{k+1} + 3 * 10^k) + (10^{k+1} + 3 * 10^k +5)\)
\(\displaystyle =9(10^{k+1} + 3 * 10^k) + 9m\) using assumption
\(\displaystyle =9(10^{k+1} + 3 * 10^k +m)\)
which is clearly divisible by \(\displaystyle 9\).
Step 4
Since\(\displaystyle P(1)\) is true AND \(\displaystyle P(k)\) true \(\displaystyle => P(k+1)\) true, then \(\displaystyle P(n)\) is true for all positive integers \(\displaystyle n\). QED
(I realise the approach using the +50-50 is much shorter and more efficient, but find younger students sometimes find it difficult to decide how to apply that technique.)
To prove: \(\displaystyle P(n): 10^{n+1} + 3 * 10^n +5 \) is divisible by \(\displaystyle 9\) for all positive integers \(\displaystyle n\).
PROOF BY INDUCTION:
Step 1
Prove true for \(\displaystyle n=1\)
\(\displaystyle P(1): 10^{(1+1)} + 3 * 10^1 + 5 =100 + 30 + 5 =135 = 9 * 15\) which is clearly a multiple of \(\displaystyle 9\)
Therefore \(\displaystyle P(1) \) is true.
Step 2
Assume true for \(\displaystyle n=k\)
ie \(\displaystyle P(k): 10^{k+1} + 3 * 10^k + 5\) is divisible by \(\displaystyle 9\)
ie \(\displaystyle 10^{k+1} + 3 * 10^k + 5 = 9m\) for some integer \(\displaystyle m\)
Step 3
Prove \(\displaystyle P(k+1): 10^{(k+1)+1} + 3 * 10^{k+1} +5\) is divisible by \(\displaystyle 9\)
Proof:
\(\displaystyle 10^{(k+1)+1} + 3 * 10^{k+1} + 5\)
\(\displaystyle =10^{k+2} + 3 * 10^{k+1} + 5\)
\(\displaystyle = 10 * 10^{k+1} + 3 * 10 * 10^k +5\)
\(\displaystyle =10(10^{k+1} + 3 * 10^k) +5\)
\(\displaystyle =(9+1)(10^{k+1} + 3 * 10^k) +5\)
\(\displaystyle =9(10^{k+1} + 3 * 10^k) +1(10^{k+1} + 3 * 10^k) +5\)
\(\displaystyle =9(10^{k+1} + 3 * 10^k) + (10^{k+1} + 3 * 10^k +5)\)
\(\displaystyle =9(10^{k+1} + 3 * 10^k) + 9m\) using assumption
\(\displaystyle =9(10^{k+1} + 3 * 10^k +m)\)
which is clearly divisible by \(\displaystyle 9\).
Step 4
Since\(\displaystyle P(1)\) is true AND \(\displaystyle P(k)\) true \(\displaystyle => P(k+1)\) true, then \(\displaystyle P(n)\) is true for all positive integers \(\displaystyle n\). QED
(I realise the approach using the +50-50 is much shorter and more efficient, but find younger students sometimes find it difficult to decide how to apply that technique.)
Last edited:
allegansveritatem
Full Member
- Joined
- Jan 10, 2018
- Messages
- 962
I will copy out what you suggest here and work with it tomorrow. I will post results then. Thanks for tip.
allegansveritatem
Full Member
- Joined
- Jan 10, 2018
- Messages
- 962
allegansveritatem
Full Member
- Joined
- Jan 10, 2018
- Messages
- 962
Thanks for the explanation. I will need to go through this in the morning when my brain revives. The symbol that looks like a hollow Z is new to me.
allegansveritatem
Full Member
- Joined
- Jan 10, 2018
- Messages
- 962
Thanks for your post. I will have to go through it in the morning when the math mood comes over me--which it unfailingly does every day for about 2 hours. Before it comes and after it goes I ain't no good for nothing in the way of 'rithmetic.
The “hollow” Z means “integer” and derives from the German verb “zahlen,” meaning to “count.”
The other symbol that may be new to you is |, which means “divides evenly“ So a | b means “a divides b evenly.“ This is meaningful only if a and b are integers. By definition
[MATH]a \ | \ b \iff a \text { and } b \text { are integers, and there exists an integer } c \text { such that } ac = b. [/MATH]
By the way, I should have mentioned that the substance of my proof is the same as pka’s. I just surrounded it with some comments on how I have found it easiest to understand finding proofs by induction.
allegansveritatem
Full Member
- Joined
- Jan 10, 2018
- Messages
- 962
So, I went at it again this morning and working through the proofs submitted to this thread I managed to come to the light. The following image is pretty much a copy of a proof from Harry the cat but I very carefully went through every step until I understood the working out:
Looking through the other proofs I came on one that had some puzzling aspects, namely that of PJA:
The -45 in the third line from the bottom...what steps were taken to get that? I think JeffM had something like this in his proof too that I wasn't quite sure of...
Am I wrong in assuming that this subject of mathematical induction is an iceberg whose dimensions are barely hinted at in a precalculus text?
Looking through the other proofs I came on one that had some puzzling aspects, namely that of PJA:
The -45 in the third line from the bottom...what steps were taken to get that? I think JeffM had something like this in his proof too that I wasn't quite sure of...
Am I wrong in assuming that this subject of mathematical induction is an iceberg whose dimensions are barely hinted at in a precalculus text?
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,086
Proofs in general are icebergs! A written proof typically hides a lot of the thinking that was needed to discover it, as we clean things up for the final presentation. A good textbook will leave more of that thinking exposed, talking at least a little about why certain things were done. But pka's version is more like the final version, lacking that explanation. The subtlety of the 45 was mentioned at the bottom of post #26 (in the guise of "+50-50", which is what was really done).
The idea there is a lot like what we do in relatively advanced "completing the square" problems. We wish we had \(10^{k+1}+3\cdot 10^k \mathbf{+5}\) inside the parentheses being multiplied by 10, and to make it so, we have to increase the expression by 50; we just subtract 50 at the same time so we don't change the value of the expression as a whole. And subtracting 50 from 5 leaves -45.
allegansveritatem
Full Member
- Joined
- Jan 10, 2018
- Messages
- 962
I see it! Very canny. Thanks
allegansveritatem
Full Member
- Joined
- Jan 10, 2018
- Messages
- 962
Thanks. I might have been exposed to these symbols a bit someplace but the sands of time.....
Here are two neat techniques that are seldom taught to beginning students, but come up from time to time.
We have an expression that is not in useful form. Say the expression is a. We need to change the expression to a useful form without changing the value.
[MATH]a \equiv a \pm 0 \equiv a + (b - b) \equiv (a + b) - b \equiv (a - b) + b.[/MATH]
[MATH]a \equiv a \cdot 1 \equiv a \cdot \dfrac{b}{b} \equiv \dfrac{ab}{b} \equiv \dfrac{a}{b} \cdot b.[/MATH]
Obviously, b must not be 0 in the previous case.
We usually take advantage of these identities going right to left and call it "simplification." But we can go from left to right if we want. I guess we should call the general process "complexification." Rationalizing denominators is about the only place it occurs in basic algebra, but both techniques can arise anywhere and are frequently useful in proofs by induction, where we are trying to state an expression in terms of another.
allegansveritatem
Full Member
- Joined
- Jan 10, 2018
- Messages
- 962
Yes, I have seen examples of this in the solutions manual I use with the text I have...but the mtext3 itself either doesn't mention this or certainly doesn't emphasize it to the point that a fairly thorough student would remember it. It certainly does come its own with mathematical induction proofs.