Prove by Induction
- Thread starter rchrist3
- Start date
HallsofIvy
Elite Member
- Joined
- Jan 27, 2012
- Messages
- 7,763
I presume you have already shown that this is true for n= 7.
"Assume for n=k" means that we can assume that \(\displaystyle 3k^2> 17k+10\)
Now, you need to think about what that would be for n= k+ 1.
\(\displaystyle 3(k+1)^2= 3(k^2+ 2k+ 1)= 3k^2+ 2k+ 1\) so the left hand side has increased by 2k+1. The right side becomes 17(k+1)+ 10 = 17k+ 10+ 17 and so has increased by 17. Can you show that 2k+1> 17?
"Assume for n=k" means that we can assume that \(\displaystyle 3k^2> 17k+10\)
Now, you need to think about what that would be for n= k+ 1.
\(\displaystyle 3(k+1)^2= 3(k^2+ 2k+ 1)= 3k^2+ 2k+ 1\) so the left hand side has increased by 2k+1. The right side becomes 17(k+1)+ 10 = 17k+ 10+ 17 and so has increased by 17. Can you show that 2k+1> 17?
You need to understand intuitively why what you are doing makes sense. Then the process will make sense.
We want to show that a proposition or statement is true for ALL integers greater than or equal to a specific integer (7 in this case).
First, we show that the statement is true for that specific integer.
Second, we show that the statement is true for integer k + 1 if the statement is true for ANY integer k that is greater or equal to the specific integer (7 in this case). We know by the first step that at least one such integer exists. OK this far?
Now let's say we succeed in this two step proof.
Well in step 1 we showed the statement is true for 7. But that means, by step 2, it is true for 8, in which case step 2 means that it is true for 9, which entails that it is true for 10, and so on, world without end. The whole row of dominoes falls one after another.
It is almost always the second part of the proof that is hard. That step requires that k be equal or greater than the specific integer. The proof must not assume that k equals the specific integer because we want step 2 to apply to bigger and bigger integers. With me so far?
The structure of the second step of the proof usually depends on the statement being true for k and for k being equal to or greater than the specific integer. I usually find that restating the proposition to be proved for k + 1 in terms of k is very helpful. So in this case
\(\displaystyle k \in \mathbb Z\ and\ k \ge 7\ and\ 3k^2 > 17k + 10 \implies\)
\(\displaystyle 3(k + 1)^2 = 3(k^2 + 2k + 1) = 3k^2 + 6k + 3.\) I restated 3(k + 1)2 in terms of k.
\(\displaystyle 17(k + 1) + 10 = 17k + 17 + 10.\) I restated 17(k + 1) + 10 in terms of k.
Now I need to prove that the first expression is greater than the second taking advantage of the facts that
\(\displaystyle 3k^2 > 17k + 10\ and\ k \ge 7.\)
Do you see how to do that?
Last edited:
Thank you for you help! so from here i realize our assumption is missing a 6k+1, so i add that to each side to prove for 3(k+1)^2 ... then from there i prove the right side of the assumption compared to the right side of the prove for (k+1)?
So when i do this i get.... 17k+10+6k+3>17k+17+10
: 23K+13>17k+27
: 23k>17k+14
:6k>14
: k> 2.3
is this right? or am i missing something... for some reason i get the feeling that this is not right
So when i do this i get.... 17k+10+6k+3>17k+17+10
: 23K+13>17k+27
: 23k>17k+14
:6k>14
: k> 2.3
is this right? or am i missing something... for some reason i get the feeling that this is not right
Last edited:
You are, I think, over-complicating this
You have:
\(\displaystyle [\alpha]\ 3(k + 1)^2 = 3k^2 + 6k + 3 = 3k^2 + (6k + 3).\)
\(\displaystyle [\beta]\ 17(k + 1) + 10 = 17k + 17 + 10 = (17k + 10) + 17.\)
\(\displaystyle [\gamma]\ k \ge 7.\)
\(\displaystyle [\delta]\ 3k^2 > (17k + 10).\)
You are right in your general thought. You have (6k + 3), which is a new expression, and 17. So let's find the relationship between them.
From gamma, I get
\(\displaystyle [\epsilon]\ 6k \ge 42 \implies (6k + 3) \ge 45 \implies (6k + 3) > 17.\)
Putting epsilon and delta together, I get
\(\displaystyle [\zeta]\ 3k^2 + (6k + 3) > (17k + 10) + 17.\)
Putting zeta together with alpha and beta, I get
\(\displaystyle 3(k + 1)^2 > 17(k + 1) + 10.\ QED\)
