math induction problem with logs

[allegansveritatem]

Here is the exercise: ( I am being asked to find the smallest possible positive integer for which the following statement is true:
I have already tested this and find that 6 is the magic number, 6 and higher which will make n true.
Here is the best of many tries:


Can anyone make anything out of this? Seems to me I might have come to the QED but maybe not. I'm not steady on my feet with these induction exercises.

 

[pka]

Have a look at this link.
Click approximate form.

 

[Deleted member 4993]

Have a look at this link.
Click approximate form.

you had a typo in the input function

 

[allegansveritatem]

Have a look at this link.
Click approximate form.

I think that there is a problem in that wolfram is working on something other than what I was working on. But it is interesting that they have such a feature as the approximate form. I will input my inequality and see what I can see. Thanks

 

[Dr.Peterson]

Here is the exercise: ( I am being asked to find the smallest possible positive integer for which the following statement is true:
View attachment 24645 I have already tested this and find that 6 is the magic number, 6 and higher which will make n true.
Here is the best of many tries:
View attachment 24646

Can anyone make anything out of this? Seems to me I might have come to the QED but maybe not. I'm not steady on my feet with these induction exercises.

I'm not quite sure how this is an induction problem. Most likely you didn't state the entire problem as given to you.

If, as you say, the problem is "find the smallest possible positive integer for which the following statement is true", haven't you found it?

Or are you saying you need to prove that it is true for all integers starting at 6? That is a different problem! To show that 6 is the smallest such integer, you just have to test 1, 2, 3, 4, 5, and 6!

And induction isn't the only way to prove what you appear to be trying to prove, so I'd guess the problem explicitly said to use induction. Please quote the exact problem, so we can be sure.

So your work is supposed to be the induction step. But I can't follow the reasoning; and you've been careless about parentheses and other bits. I'll take a look at how I'd do it, while you try again, being a little more careful. Keep in mind what you are assuming and what you need to show; don't start from the latter.

 

[lookagain]

View attachment 24646

Can anyone make anything out of this?

From the second line (that is showing) to the next line, you changed the less
than or equals to symbol to a strictly less than symbol. Also, on the fourth
line, you do not have grouping symbols around k + 1. I did not continue
looking beyond that.

 

[Steven G]

For n>0, log₂n >0. After adding this positive number to 20 we have that the sum >20. Since 4^2 not >20 and 5^2 is more than 20 I would start checking from n=5.

 

[lookagain]

For n>0, log₂n >0.

Where n is an integer, for \(\displaystyle \ n > 1, \ log_2{(n)} > 0.\)

\(\displaystyle log_2{(1)} \ = \ 0 \)

 

[allegansveritatem]

I'm not quite sure how this is an induction problem. Most likely you didn't state the entire problem as given to you.

If, as you say, the problem is "find the smallest possible positive integer for which the following statement is true", haven't you found it?

Or are you saying you need to prove that it is true for all integers starting at 6? That is a different problem! To show that 6 is the smallest such integer, you just have to test 1, 2, 3, 4, 5, and 6!

And induction isn't the only way to prove what you appear to be trying to prove, so I'd guess the problem explicitly said to use induction. Please quote the exact problem, so we can be sure.

So your work is supposed to be the induction step. But I can't follow the reasoning; and you've been careless about parentheses and other bits. I'll take a look at how I'd do it, while you try again, being a little more careful. Keep in mind what you are assuming and what you need to show; don't start from the latter.

Right. There are two parts to this: a)Find the smallest positive integer that will ring the "true bell" and b) Prove by induction that for said integer and above this is also true.
I will give this another go today, correcting what I can correct and see. This stuff is hard in that it is open-ended with lots of options.

 

[allegansveritatem]

For n>0, log₂n >0. After adding this positive number to 20 we have that the sum >20. Since 4^2 not >20 and 5^2 is more than 20 I would start checking from n=5.

Well, I tried trial and error and did not find 5 fit the bill. 31 is more than 25. It was no great problem here to find the cut-off point. I can see how it might be nice to have a formula or a method, however, to get into the ballpark in these matters.

 

[Dr.Peterson]

Right. There are two parts to this: a)Find the smallest positive integer that will ring the "true bell" and b) Prove by induction that for said integer and above this is also true.
I will give this another go today, correcting what I can correct and see. This stuff is hard in that it is open-ended with lots of options.

"Ring the 'true bell'"? Is that explained in the problem, or are you still paraphrasing?

I'm sure you've been told this before, but we ask you for good reason the STATE THE ENTIRE PROBLEM exactly:

Posting Guidelines (Summary)

Welcome to our tutoring boards! :) This page summarizes the main points from our posting guidelines. As our name implies, we provide math help (primarily to students with homework). We do not generally post immediate answers or step-by-step solutions. We don't do your homework. We prefer to...

www.freemathhelp.com

Not doing so wastes a lot of time!

Now, I haven't yet worked out an inductive proof of this myself; it doesn't seem particularly easy. Have you told us anything about your current context, that is, what sort of inductive proofs you have seen? If I were helping you face to face, I would be looking through your book to see if they have given any examples that might give a hint how to approach it, because they would likely have done something to prepare you; inequalities can be particularly tricky.

And, yes, proofs in general are "open-ended with lots of options", which makes it important to be patient!

 

[Steven G]

Where n is an integer, for \(\displaystyle \ n > 1, \ log_2{(n)} > 0.\)

\(\displaystyle log_2{(1)} \ = \ 0 \)

yes, yes, I did think n>1 but somehow wrote n>0. The rest of my post assumed that n>1

 

[JeffM]

I have been thinking on and off about this problem. I thought I had found an elegant proof, but I was wrong. There probably is an elegant proof, but I have not found it.

I remember saying to you about induction that proving the base step can sometimes tell you something of use for the induction step. How did you prove that P(n) is false if n < 6 and P(6) is true? A calculator does not cut it: the calculator may have a flaw, and it certainly will not tell you anything that can be generalized.

Here is my proof of that initial step.

[MATH]\text {Let } y(n) = nlog_2(n) + 20 \land z(n) = n^2[/MATH]
[MATH]n = 1 \implies z(n) = 1 \land log_2(1) = 0 \implies y(n) = 20 \implies z(n) < y(n).[/MATH]
[MATH]n = 2 \implies z(n) = 4 \land log_2(2) = 1 \implies y(n) = 22 \implies z(n) < y(n).[/MATH]
[MATH]n = 3 \implies z(n) = 9 \land 1 < log_2(3) < 2 \implies 23 < y(n) < 26 \implies z(n) < y(n).[/MATH]
[MATH]n = 4 \implies z(n) = 16 \land log_2(4) = 2 \implies y(n) = 28 \implies z(n) < y(n).[/MATH]
[MATH]n = 5 \implies z(n) = 25 \land 2 < log_2(3) < 3 \implies 30 < y(n) < 35 \implies z(n) < y(n).[/MATH]
That proves that P(n) is false if n < 6. Unfortunately, this simple approach does not work for 6. It is too crude because we get

32 < y(6) < 38 and 6^2 = 36. We need to be slightly more restrictive.

[MATH]128 < 216 < 256 \implies 2^7 < 6^3 < 2^8 \implies 2^{7/3} < 6 < 2^{8/3} \implies[/MATH]
[MATH]log_2(2^{7/3}) < log_2(6) < log_2(2^{8/3}) \implies 2 < \dfrac{7}{3} < log_2(6) < \dfrac{8}{3} < 3.[/MATH]
[MATH]\therefore 14 + 20 < 6 \sqrt{6} + 20 < 16 + 20 \implies y(6) < 36 = z(n).[/MATH]
So P(6)) is true.

Now this just gives us the base case, but I would be amazed if an induction step cannot be built from these ideas.

 

[allegansveritatem]

"Ring the 'true bell'"? Is that explained in the problem, or are you still paraphrasing?

I'm sure you've been told this before, but we ask you for good reason the STATE THE ENTIRE PROBLEM exactly:

Posting Guidelines (Summary)

Welcome to our tutoring boards! :) This page summarizes the main points from our posting guidelines. As our name implies, we provide math help (primarily to students with homework). We do not generally post immediate answers or step-by-step solutions. We don't do your homework. We prefer to...

www.freemathhelp.com

Not doing so wastes a lot of time!

Now, I haven't yet worked out an inductive proof of this myself; it doesn't seem particularly easy. Have you told us anything about your current context, that is, what sort of inductive proofs you have seen? If I were helping you face to face, I would be looking through your book to see if they have given any examples that might give a hint how to approach it, because they would likely have done something to prepare you; inequalities can be particularly tricky.

And, yes, proofs in general are "open-ended with lots of options", which makes it important to be patient!

I will be careful henceforth to include a statement of the whole task at hand.
I can tell you that while the text did have one example of an inequality being solved, this particular flavor of that breed was not broached in the body of the section BUT there was a problem in the exercises with a solution worked out in the solutions manual that was of great help to me. So I am thinking that Dr. Stokowski, the author, must have expected students to not only do most or all of the exercises after each section but also to have the solutions manual to refer to in times of great duress. I would be lost without that solutions manual.Of course, the author also expected most students would have a teacher or professor there to guide them as well.
Anyway, I went at it again today and I think I did a little better:

 

[allegansveritatem]

I have been thinking on and off about this problem. I thought I had found an elegant proof, but I was wrong. There probably is an elegant proof, but I have not found it.

I remember saying to you about induction that proving the base step can sometimes tell you something of use for the induction step. How did you prove that P(n) is false if n < 6 and P(6) is true? A calculator does not cut it: the calculator may have a flaw, and it certainly will not tell you anything that can be generalized.

Here is my proof of that initial step.

[MATH]\text {Let } y(n) = nlog_2(n) + 20 \land z(n) = n^2[/MATH]
[MATH]n = 1 \implies z(n) = 1 \land log_2(1) = 0 \implies y(n) = 20 \implies z(n) < y(n).[/MATH]
[MATH]n = 2 \implies z(n) = 4 \land log_2(2) = 1 \implies y(n) = 22 \implies z(n) < y(n).[/MATH]
[MATH]n = 3 \implies z(n) = 9 \land 1 < log_2(3) < 2 \implies 23 < y(n) < 26 \implies z(n) < y(n).[/MATH]
[MATH]n = 4 \implies z(n) = 16 \land log_2(4) = 2 \implies y(n) = 28 \implies z(n) < y(n).[/MATH]
[MATH]n = 5 \implies z(n) = 25 \land 2 < log_2(3) < 3 \implies 30 < y(n) < 35 \implies z(n) < y(n).[/MATH]
That proves that P(n) is false if n < 6. Unfortunately, this simple approach does not work for 6. It is too crude because we get

32 < y(6) < 38 and 6^2 = 36. We need to be slightly more restrictive.

[MATH]128 < 216 < 256 \implies 2^7 < 6^3 < 2^8 \implies 2^{7/3} < 6 < 2^{8/3} \implies[/MATH]
[MATH]log_2(2^{7/3}) < log_2(6) < log_2(2^{8/3}) \implies 2 < \dfrac{7}{3} < log_2(6) < \dfrac{8}{3} < 3.[/MATH]
[MATH]\therefore 14 + 20 < 6 \sqrt{6} + 20 < 16 + 20 \implies y(6) < 36 = z(n).[/MATH]
So P(6)) is true.

Now this just gives us the base case, but I would be amazed if an induction step cannot be built from these ideas.

I came to the same thing you did but used a more primitive method or at least a sloppier form of the same method, namely, trial and error. I know that a calculator is useless with this type of problem but it has great use in the trial and error Please check my latest attempt at the last stage of the process posted just now above. I think maybe I got it--although I am still a bit wobbly with regard to the placement of the more than/less than signs.

 

[JeffM]

I came to the same thing you did but used a more primitive method or at least a sloppier form of the same method, namely, trial and error. I know that a calculator is useless with this type of problem but it has great use in the trial and error Please check my latest attempt at the last stage of the process posted just now above. I think maybe I got it--although I am still a bit wobbly with regard to the placement of the more than/less than signs.

I shall look at it in the morning. It is late, and I have had a few drinks. A glance suggests to me that you are on the right track, but I need to be awake to do math.

I think you missed my meaning about the calculator because I was being a bit flippant in tone.

There is NOTHING WRONG WITH USING A CALCULATOR FOR EXPLORING

My primary point was that the calculator gives you no insight into the problem.

 

[jonah2.0]

Beer soaked clarification follows.

Here is the exercise: ( I am being asked to find the smallest possible positive integer for which the following statement is true:
View attachment 24645 I have already tested this and find that 6 is the magic number, 6 and higher which will make n true.
Here is the best of many tries:
View attachment 24646

Can anyone make anything out of this? Seems to me I might have come to the QED but maybe not. I'm not steady on my feet with these induction exercises.

The exact words were:

Find the smallest positive integer `j` for which the statement is true. Use the extended principle of mathematical induction to prove that the formula is true for every integer greater than `j`.

 

[Dr.Peterson]

I will be careful henceforth to include a statement of the whole task at hand.
I can tell you that while the text did have one example of an inequality being solved, this particular flavor of that breed was not broached in the body of the section BUT there was a problem in the exercises with a solution worked out in the solutions manual that was of great help to me. So I am thinking that Dr. Stokowski, the author, must have expected students to not only do most or all of the exercises after each section but also to have the solutions manual to refer to in times of great duress. I would be lost without that solutions manual.Of course, the author also expected most students would have a teacher or professor there to guide them as well.
Anyway, I went at it again today and I think I did a little better:
View attachment 24697

Much better; but the fourth line is missing a term.

 

[JeffM]

Couple of things.

Knowing that P(6) is true, we can say that there is at least one integer > 5 for which P is true. Let k be any such integer.

[MATH]\therefore k \text { is an integer } > 5 \land k \cdot log_2 (k) + 20 \le k^2 \implies [/MATH]
[MATH]k \cdot log_2(k) \le k^2 - 20.[/MATH]
I think it is really helpful to state the “induction hypothesis” and any consequence likely to be of use EXPLICITLY. Then they are right there for you to see without burdening your memory.

Second thing. You assume without mentioning that 2k > k + 1. It is critical to the proof.

[MATH]k > 5 \implies k + k > k + 5 \implies 2k > (k + 1) + 4 \implies 2k > k + 1.[/MATH]
Third thing. Remember that you will need a 2k on the right hand side. You must figure out where to get it.

[MATH]k + 1 < 2k \implies log_2(k + 1) < log_2(2k) \implies (k + 1) \cdot log_2(k + 1) < (k + 1) \cdot log_2(2k) =[/MATH]
[MATH](k + 1)\{ log_2(k) + log_2(2)\} = (k + 1)\{log_2(k) + 1\} = k \cdot log_2(k) + k + log_2(k) + 1.[/MATH]
Where do you want to end up? With [MATH]k^2 + 2k + 1 = (k + 1)^2.[/MATH]
That log_2(k) is a pain. BUT THIS IS AN INEQUALITY.

[MATH]log_2(k) < k \implies k \cdot log_2(k) + k + log_2(k) + 1 < k \cdot log_2(k) + 2k + 1.[/MATH]
[MATH]\text {And } k \cdot log_2(k) \le k^2 - 20 \implies [/MATH]
[MATH](k + 1) \cdot log_2( k + 1) < k^2 - 20 + 2k + 1 = (k^2 + 2k + 1) - 20 = (k + 1)^2 - 20.[/MATH]
[MATH]\therefore (k + 1) \cdot log_2(k + 1) + 20 \le (k + 1)^2.[/MATH]

 

[allegansveritatem]

Beer soaked clarification follows.

The exact words were:

Find the smallest positive integer `j` for which the statement is true. Use the extended principle of mathematical induction to prove that the formula is true for every integer greater than `j`.
View attachment 24702

Yes, I neglected to add that last sentence--a grave omission, that.