math induction problem with logs

[allegansveritatem]

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

Right but then the term miraculously appeared again below! By this time I had gone through this problem so many times that I couldn't lose anything for long.

 

[allegansveritatem]

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]

I am going to get a snapshot of this and study it tomorrow when I am doing my math work. I realize I was doing things that I couldn't quite justify. I will work through this tomorrow and post a new attempt. Thanks for going through it. This kind of problem can get mean and nasty. Two or three problems down from this one we are asked to prove De Moivre's Theorem! I read this and, after regaining consciousness, I went straigiht to the solutions manual and found that the solution was as mystifying as the problem. For the life of me I couldn't find the sine cosine addition formulas that were supposed to be used to work the thing out. I know what these formulas are but how in the world they had been worked into the solution completely escaped me. Happy me that I found a couple of Youtube videos where this problem is the featured subject. I am going to watch them all and try De Moivre again. God, he is bad enough without having to prove him!

 

[JeffM]

I am going to get a snapshot of this and study it tomorrow when I am doing my math work. I realize I was doing things that I couldn't quite justify. I will work through this tomorrow and post a new attempt. Thanks for going through it. This kind of problem can get mean and nasty. Two or three problems down from this one we are asked to prove De Moivre's Theorem! I read this and, after regaining consciousness, I went straigiht to the solutions manual and found that the solution was as mystifying as the problem. For the life of me I couldn't find the sine cosine addition formulas that were supposed to be used to work the thing out. I know what these formulas are but how in the world they had been worked into the solution completely escaped me. Happy me that I found a couple of Youtube videos where this problem is the featured subject. I am going to watch them all and try De Moivre again. God, he is bad enough without having to prove him!

ROFL

 

[Dr.Peterson]

Right but then the term miraculously appeared again below! By this time I had gone through this problem so many times that I couldn't lose anything for long.

Not the term I'm talking about!

 

[allegansveritatem]

Not the term I'm talking about!

Which are you referring to?

 

[allegansveritatem]

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]

So, I studied this today until I felt I understood it and then I put it aside and worked out the problem again and came up with this:

 

[Dr.Peterson]

Which are you referring to?

Here are the third and fourth lines:



When you distribute, you get \(k\log_2(k)+k+\log_2(k)+1\); you don't have the third term.

 

[JeffM]

So, I studied this today until I felt I understood it and then I put it aside and worked out the problem again and came up with this:
View attachment 24742

Tomorrow

 

[Dr.Peterson]

There's a problem like the previous one I mentioned, here:



You must have been thinking \(k\log_2(2k)=k(\log(k)+1)\). Do you see the difference? The first line here is less than the second only if \(k<1\).

Also, how do you know this?

 

[allegansveritatem]

There's a problem like the previous one I mentioned, here:

View attachment 24757

You must have been thinking \(k\log_2(2k)=k(\log(k)+1)\). Do you see the difference? The first line here is less than the second only if \(k<1\).

Also, how do you know this?

View attachment 24758

1) Yes,, I see. I forgot to multiply the 1 by k. I will go back over this today and see how this new information will inflect (or deflect) the trajectory of my proof,
2) My thought was: 2k is greater than k+1-as I showed earlier in this proof- so from that it seemed to flow naturally that the log of k+1 would be considerably less than 2k...no?

 

[Dr.Peterson]

2) My thought was: 2k is greater than k+1-as I showed earlier in this proof- so from that it seemed to flow naturally that the log of k+1 would be considerably less than 2k...no?

You need to either prove it, or refer to a theorem that supports the claim (which someone else will have proved).

 

[JeffM]

2) My thought was: 2k is greater than k+1-as I showed earlier in this proof- so from that it seemed to flow naturally that the log of k+1 would be considerably less than 2k...no?

I saw the same comment by Dr. Peterson and initially had the same reaction that you did. Then I realized the subtlety of his comment.

[MATH]k > log_2(k) \implies 2k > k > log_2(k) \ \because \ k > 0.[/MATH]
And in my derivation I had said [MATH]k > log_2(k).[/MATH]
I gave absolutely no justification for that proposition. That is a problem with derivations. I (and you) have no idea what theorems are assumed to be available for use.

I was relying on this theorem:

[MATH]b > 1 \land x > 0 \implies x > log_b(x).[/MATH]
Clearly 2 > 1 so all is well.

But then I realized that I have no clue how to prove that theorem without using calculus, and you are studying algebra rather than calculus. I am not saying that I could not figure out how to prove that theorem using only algebra, but that might be a harder problem than the one we are working on.

 

[allegansveritatem]

You need to either prove it, or refer to a theorem that supports the claim (which someone else will have proved).

If that is the case...then my latest piece of work, which I post below, is not correct? I must say that I don't see how it can be contested that 2k is greater than k+1 seeing that k has to be greater than 6. Anyway, here is what I did today:

 

[allegansveritatem]

I saw the same comment by Dr. Peterson and initially had the same reaction that you did. Then I realized the subtlety of his comment.

[MATH]k > log_2(k) \implies 2k > k > log_2(k) \ \because \ k > 0.[/MATH]
And in my derivation I had said [MATH]k > log_2(k).[/MATH]
I gave absolutely no justification for that proposition. That is a problem with derivations. I (and you) have no idea what theorems are assumed to be available for use.

I was relying on this theorem:

[MATH]b > 1 \land x > 0 \implies x > log_b(x).[/MATH]
Clearly 2 > 1 so all is well.

But then I realized that I have no clue how to prove that theorem without using calculus, and you are studying algebra rather than calculus. I am not saying that I could not figure out how to prove that theorem using only algebra, but that might be a harder problem than the one we are working on.

if such is the case then how can we break up the term klog(k+1)? And it has to be broken up.

 

[Dr.Peterson]

If that is the case...then my latest piece of work, which I post below, is not correct? I must say that I don't see how it can be contested that 2k is greater than k+1 seeing that k has to be greater than 6. Anyway, here is what I did today:
View attachment 24789

No step of your work is false; it is true that \(k > log_2(k)\) for all k. But that wouldn't be true, for example, of \(\log_{1.4}(x)\), for which it would still be true if you require k to be greater than, say, 5. (I know that at the moment only from graphing!) So we can't just say it's obvious.

All that's missing is a proof of that fact that is appropriate at your level (without calculus).

This is another of those cases where, if I were working with you in person, I would be leafing through your book to see whether there is anything they've said that could be useful. For example, it could be that they have previously proved it for all positive integers k by induction (I believe I've done that), in an example or exercise, and you are allowed to use that result. Or they may have proved the equivalent fact that \(2^x > x\) for all x.

Or maybe there is an easier way that works around this step; I'll admit I haven't sat down and tried to work this out completely myself. I'll go do it.

 

[JeffM]

if such is the case then how can we break up the term klog(k+1)? And it has to be broken up.

Oh, I have no doubt that it is true for bases greater than 2. And I did not hesitate to use it in this kind of exercise. But, strictly speaking, using it without proof or citation of a proof means that what I did is incomplete.

I do not see how it can be proved for positive real numbers without some calculus.

It could however be stated as an axiom, a law of logs, and then the proof would be complete.

 

[allegansveritatem]

No step of your work is false; it is true that \(k > log_2(k)\) for all k. But that wouldn't be true, for example, of \(\log_{1.4}(x)\), for which it would still be true if you require k to be greater than, say, 5. (I know that at the moment only from graphing!) So we can't just say it's obvious.

All that's missing is a proof of that fact that is appropriate at your level (without calculus).

This is another of those cases where, if I were working with you in person, I would be leafing through your book to see whether there is anything they've said that could be useful. For example, it could be that they have previously proved it for all positive integers k by induction (I believe I've done that), in an example or exercise, and you are allowed to use that result. Or they may have proved the equivalent fact that \(2^x > x\) for all x.

Or maybe there is an easier way that works around this step; I'll admit I haven't sat down and tried to work this out completely myself. I'll go do it.

well, I can say that in the directions at the head of this series of problems we are told that graphing is one way we can find j, j being the first in a series of integers (that then extends to infinity, so to speak, in one direction) for which the inequality is true. As for what the author of the book accepts, I don't have access to the book where I am just now but I can say that I seem to recall in the solutions manual a case in the solution of one of these problems where the inequality k is greater than log two k is allowed as self-evident considering the constraints on k, I will look later on today and see what I can see. But I see your point: A proof has to be bullet-proof to every extent possible.

 

[allegansveritatem]

Oh, I have no doubt that it is true for bases greater than 2. And I did not hesitate to use it in this kind of exercise. But, strictly speaking, using it without proof or citation of a proof means that what I did is incomplete.

I do not see how it can be proved for positive real numbers without some calculus.

It could however be stated as an axiom, a law of logs, and then the proof would be complete.

I will search through the text later for that axiom. I know this book pretty well by now and don't actually recall it, but memory , as the feller once said, is a treacherous friend, and I can assert under oath that it doesn't get any less treacherous over time.

 

[Dr.Peterson]

well, I can say that in the directions at the head of this series of problems we are told that graphing is one way we can find j, j being the first in a series of integers (that then extends to infinity, so to speak, in one direction) for which the inequality is true. As for what the author of the book accepts, I don't have access to the book where I am just now but I can say that I seem to recall in the solutions manual a case in the solution of one of these problems where the inequality k is greater than log two k is allowed as self-evident considering the constraints on k, I will look later on today and see what I can see. But I see your point: A proof has to be bullet-proof to every extent possible.

As we've said before, it's a really good idea to quote the entire problem, including such directions. It sounds like your OP here was entirely misdirected, as they were encouraging you to find that base case any way you want, not requiring a proof for that part, or even an efficient way to find it.

It may be that your book isn't really pushing the idea of bullet-proof proofs, and you're expected to be a little [too] relaxed about such details. That's another reason I'd want to leaf through the book, just to get a sense of its style and level. What book is it?

 

[jonah2.0]

Beer induced recall follows.

As we've said before, it's a really good idea to quote the entire problem, including such directions. It sounds like your OP here was entirely misdirected, as they were encouraging you to find that base case any way you want, not requiring a proof for that part, or even an efficient way to find it.

It may be that your book isn't really pushing the idea of bullet-proof proofs, and you're expected to be a little [too] relaxed about such details. That's another reason I'd want to leaf through the book, just to get a sense of its style and level. What book is it?

He mentioned the author a few weeks ago at:

Beer soaked query follows.
From which book did you get your conundrum?

Earl Swokowski