Induction

[mperez2k]

Hello! I am sorry to be posting this thread, but I really need your help. Please don't ban me with this. Thank you.

My problem is about induction. I really can't get it. One of the problems which my professor gave was:

n² < 4ⁿ

Here's my solution: (don't know if this is right)

I started in the base step which is letting n=1. (Because it was taught by my professor.)
So in my step 1:
Let n=1
n² < 4ⁿ
n²=1 and 4ⁿ=4
1<4 so it's true when n=1

Then in my step 2, I assumed that P(k+1) is true.
So, k² < 4^k
Then, based on what I have known and read from discussions and online readings, this is what i did next:
k² < 4^k+1
4(k²) < 4(4^k)
1st: 4k² < 4^k+1

Then,
2nd: (k+1)² < 4^k+1

Then based on what I have seen on the internet, I did this:
(k+1)² < 4k² <-----(This is my 1st question. Why do I need to do this? My professor didn't even taught me that.)

Then I solved the inequality:
(k+1)² < 4k²
k²+2k+1 < 4k²
0 < 3k²-2k-1

Rewriting,
3k²-2k-1 > 0

Completing the square,
k²-(2/3)k-(1/3) > 0
k²-(2/3)k+(1/9) > (1/3)+(1/9)
(k-(1/3))² > 4/9

I got their square roots,
k-(1/3) > 2/3
k > (2/3)+(1/3)

I got,

k > 1 <----(This is my second question, is this where I stop? What's the importance of getting this? I need an explanation with this.)



My final question is: Was my solution right? And any recommendations you can give so that I'll not get difficulty when solving problems like this?

So that's it. That's what I got. I really had no idea, I just searched the internet on how to do induction.
I really hope you can help me with this.

And please, answer my questions at the top. I also really need an easiest way on how to do induction. For example, what should I really need to find out in step 1, step 2, and so on. This will surely help me ace my exam this coming week. Thank you.

 

[mperez2k]

Sorry for this, but I really need an immediate answer. I really need this to be reviewed so that I could get a high score. Thanks.

 

[Deleted member 4993]

Hello! I am sorry to be posting this thread, but I really need your help. Please don't ban me with this. Thank you.

My problem is about induction. I really can't get it. One of the problems which my professor gave was:

n² < 4ⁿ

Here's my solution: (don't know if this is right)

I started in the base step which is letting n=1. (Because it was taught by my professor.)
So in my step 1:
Let n=1
n² < 4ⁿ
n²=1 and 4ⁿ=4
1<4 so it's true when n=1

Then in my step 2, I assumed that P(k+1) is true.
So, k² < 4^k
Then, based on what I have known and read from discussions and online readings, this is what i did next:
k² < 4^k+1
4(k²) < 4(4^k)
1st: 4k² < 4^k+1

Then,
2nd: (k+1)² < 4^k+1

Then based on what I have seen on the internet, I did this:
(k+1)² < 4k² <-----(This is my 1st question. Why do I need to do this? My professor didn't even taught me that.)

Then I solved the inequality:
(k+1)² < 4k²
k²+2k+1 < 4k²
0 < 3k²-2k-1

Rewriting,
3k²-2k-1 > 0

Completing the square,
k²-(2/3)k-(1/3) > 0
k²-(2/3)k+(1/9) > (1/3)+(1/9)
(k-(1/3))² > 4/9

I got their square roots,
k-(1/3) > 2/3
k > (2/3)+(1/3)

I got,

k > 1 <----(This is my second question, is this where I stop? What's the importance of getting this? I need an explanation with this.)



My final question is: Was my solution right? And any recommendations you can give so that I'll not get difficulty when solving problems like this?

So that's it. That's what I got. I really had no idea, I just searched the internet on how to do induction.
I really hope you can help me with this.

And please, answer my questions at the top. I also really need an easiest way on how to do induction. For example, what should I really need to find out in step 1, step 2, and so on. This will surely help me ace my exam this coming week. Thank you.

4ⁿ > n² for n=1

assume 4ⁿ > n²

4ⁿ⁺¹ = 4 * 4ⁿ > 4 * n² = (2n)² > (n+1)² for 2n > n+1 or n > 1

Thus

4ⁿ⁺¹ > (n+1)² for n > 1

 

[HallsofIvy]

Hello! I am sorry to be posting this thread, but I really need your help. Please don't ban me with this. Thank you.

My problem is about induction. I really can't get it. One of the problems which my professor gave was:

n² < 4ⁿ

wasn't there something about "n is a positive integer" or "\(\displaystyle n\in N\)"?

Here's my solution: (don't know if this is right)

I started in the base step which is letting n=1. (Because it was taught by my professor.)
So in my step 1:
Let n=1
n² < 4ⁿ
n²=1 and 4ⁿ=4
1<4 so it's true when n=1

So far so good!

Then in my step 2, I assumed that P(k+1) is true.

.
No, you are assuming that P(k) is true for some positive integer k.

So, k² < 4^k
Then, based on what I have known and read from discussions and online readings, this is what i did next:
k² < 4^k+1

That happens to be true because 4> 1 so \(\displaystyle 4^k(1)< 4^k(k)= 4^{k+1}

4(k²) < 4(4^k)

But this does not follow from your previous line. It does follow from the line before that, that \(\displaystyle k^2< 4^k\)
by multiplying both sides by 4.

1st: 4k² < 4^k+1

Then,
2nd: (k+1)² < 4^k+1

What? This is what you want to prove isn't it? It doesn't follow from what you said above unless you have already proven that \(\displaystyle (k+1)^2< 4k^2\) and that isn't true. For example, if k= 1, then \(\displaystyle (k+ 1)^2= (1+ 1)^2= \) which is NOT less that \(\displaystyle 4k^2= 4\).

Then based on what I have seen on the internet, I did this:
(k+1)² < 4k² <-----(This is my 1st question. Why do I need to do this? My professor didn't even taught me that.)

As I just said, you need it in order that your previous step be true. Why you need to do that depends upon why you chose to write the previous statement! But you can't just write, you still need to prove it is true! And as I just said, also, it is NOT true for all k.

Then I solved the inequality:
(k+1)² < 4k²
k²+2k+1 < 4k²
0 < 3k²-2k-1

Rewriting,
3k²-2k-1 > 0

Completing the square,
k²-(2/3)k-(1/3) > 0
k²-(2/3)k+(1/9) > (1/3)+(1/9)
(k-(1/3))² > 4/9

I got their square roots,
k-(1/3) > 2/3

You are aware that an equation like \(\displaystyle (k- (1/3))^2= 4/9 has two roots aren't you ?
A somewhat simpler method would have been to factor: \(\displaystyle 3k^2- 2k- 1= (k- 1)(3k+ 1)\) and is equal to 0 when k= 1 or k= -1/3.

k > (2/3)+(1/3)

This is partly correct.

I got,

k > 1 <----(This is my second question, is this where I stop? What's the importance of getting this? I need an explanation with this.)

What question does "k> 1" answer? And if you don't know that why were you trying to find that? Look back through each step and try decide why you did that step.

My final question is: Was my solution right? And any recommendations you can give so that I'll not get difficulty when solving problems like this?

So that's it. That's what I got. I really had no idea, I just searched the internet on how to do induction.
I really hope you can help me with this.

And please, answer my questions at the top. I also really need an easiest way on how to do induction. For example, what should I really need to find out in step 1, step 2, and so on. This will surely help me ace my exam this coming week. Thank you.

\)\)

 

[mperez2k]

wasn't there something about "n is a positive integer" or "\(\displaystyle n\in N\)"?


So far so good!

.
No, you are assuming that P(k) is true for some positive integer k.


That happens to be true because 4> 1 so \(\displaystyle 4^k(1)< 4^k(k)= 4^{k+1}


But this does not follow from your previous line. It does follow from the line before that, that \(\displaystyle k^2< 4^k\)
by multiplying both sides by 4.


What? This is what you want to prove isn't it? It doesn't follow from what you said above unless you have already proven that \(\displaystyle (k+1)^2< 4k^2\) and that isn't true. For example, if k= 1, then \(\displaystyle (k+ 1)^2= (1+ 1)^2= \) which is NOT less that \(\displaystyle 4k^2= 4\).


As I just said, you need it in order that your previous step be true. Why you need to do that depends upon why you chose to write the previous statement! But you can't just write, you still need to prove it is true! And as I just said, also, it is NOT true for all k.


You are aware that an equation like \(\displaystyle (k- (1/3))^2= 4/9 has two roots aren't you ?
A somewhat simpler method would have been to factor: \(\displaystyle 3k^2- 2k- 1= (k- 1)(3k+ 1)\) and is equal to 0 when k= 1 or k= -1/3.


This is partly correct.


What question does "k> 1" answer? And if you don't know that why were you trying to find that? Look back through each step and try decide why you did that step.\)\)

\(\displaystyle \(\displaystyle

Oh. I forgot to tell that yes you're right. It has [FONT=MathJax_Math]n[/FONT][FONT=MathJax_Main]∈ N

Actually, I also didn't get it. The part which has "1st" and "2nd". It just says from the internet that I should do (k+1)²<4k² < 4^k+1
So That is the thing I don't get. Where did they get that? Or what's that? I really don't know that, though I read some induction articles on the internet.

Sorry for my solution because I don't really know what's going on with the middle part of induction. I only know the base step and the step which is assuming that P(k) is true.
(By the way, sorry for my typo error on that, it must be P(k) is true, instead of P(k+1))

So I solved for this, (k+1)²<4k²
Then I got to solve the inequality.
One thing I want to know is for what is the k>1? Why do I need to solve for it? It's importance is what? I really don't know it because it wasn't really taught well.
[/FONT]\)\)

 

[mperez2k]

4ⁿ > n² for n=1

assume 4ⁿ > n²

4ⁿ⁺¹ = 4 * 4ⁿ > 4 * n² = (2n)² > (n+1)² for 2n > n+1 or n > 1

Thus

4ⁿ⁺¹ > (n+1)² for n > 1

I have a question. For what is the (2n)² > (n+1)² ?
Where did you get the (n+1)? I am a bit confused with it.
Sorry, i really can't see your solution properly. Thank you.

 

[JeffM]

Hello! I am sorry to be posting this thread, but I really need your help. Please don't ban me with this. Thank you.

My problem is about induction. I really can't get it. One of the problems which my professor gave was:

n² < 4ⁿ

Here's my solution: (don't know if this is right)

I started in the base step which is letting n=1. (Because it was taught by my professor.)
So in my step 1:
Let n=1
n² < 4ⁿ
n²=1 and 4ⁿ=4
1<4 so it's true when n=1

Then in my step 2, I assumed that P(k+1) is true. NO
So, k² < 4^k
Then, based on what I have known and read from discussions and online readings, this is what i did next:
k² < 4^k+1
4(k²) < 4(4^k)
1st: 4k² < 4^k+1

Then,
2nd: (k+1)² < 4^k+1

Then based on what I have seen on the internet, I did this:
(k+1)² < 4k² <-----(This is my 1st question. Why do I need to do this? My professor didn't even taught me that.)

Then I solved the inequality:
(k+1)² < 4k²
k²+2k+1 < 4k²
0 < 3k²-2k-1

Rewriting,
3k²-2k-1 > 0

Completing the square,
k²-(2/3)k-(1/3) > 0
k²-(2/3)k+(1/9) > (1/3)+(1/9)
(k-(1/3))² > 4/9

I got their square roots,
k-(1/3) > 2/3
k > (2/3)+(1/3)

I got,

k > 1 <----(This is my second question, is this where I stop? What's the importance of getting this? I need an explanation with this.)



My final question is: Was my solution right? And any recommendations you can give so that I'll not get difficulty when solving problems like this?

So that's it. That's what I got. I really had no idea, I just searched the internet on how to do induction.
I really hope you can help me with this.

And please, answer my questions at the top. I also really need an easiest way on how to do induction. For example, what should I really need to find out in step 1, step 2, and so on. This will surely help me ace my exam this coming week. Thank you.

Let's talk intuitively first about the proof of propositions by weak mathematical induction.

It works this way: first you prove that a proposition about the positive integers is true for 1. Second you prove that if it is true for any integer k not less than 1, it is also true for (k + 1).

So because it is true for 1 (by the first step), it is also true for 2 (by the second step), but that means (again by the second step) that it is true for 3, which entails that the second step makes it true for 4, which means it is valid for 5, and so on forever. The whole row of dominoes falls. Very intuitive, very simple.

More formally, you prove the proposition true for 1, which you did. That is step 1 in every proof by mathematical induction.

Step 2 is harder. You consider ANY integer k that is NOT less than 1 for which the proposition is true. You KNOW that at least one such integer exists because you proved that ONE was such an integer earlier. However, you must NOT assume that k = 1 because, to make the dominoes fall, it must be true for ever bigger integers.

\(\displaystyle STEP\ 1:\ 1^2 = 1 < 4 = 4^1 \implies n^2 < 4^n\ if\ n\ is\ an\ integer = 1.\)

\(\displaystyle STEP\ 2:\ Let\ k\ be\ any\ integer\ such\ that\ k \ge 1\ and\ k^2 < 4^k.\)

There is at least one such integer, namely 1, but you are NOT assuming that k = 1. This is key to the logic.

\(\displaystyle 4^{(k+1)} = 4 * 4^k.\) I am going to try to reduce the terms of the proposition for k + 1 to k and KNOWN integers.

\(\displaystyle And\ (k + 1)^2 = k^2 + 2k + 1.\) Clear so far?

Now if I could prove that \(\displaystyle k^2 + 2k + 1 < 4 * 4^k,\) I have the required proof.

\(\displaystyle 1 \le k \implies 1^2 \le k^2 \implies 1 \le k^2.\)

\(\displaystyle 1 \le k \implies (2k * 1) \le (2k * k) \implies 2k \le 2k^2.\)

\(\displaystyle So\ k^2 + 2k + 1 \le k^2 + 2k^2 + k^2 = 4k^2.\)

\(\displaystyle But\ 4k^2 < 4 * 4^k.\)

\(\displaystyle So\ k^2 + 2k + 1 < 4 * 4^k.\)

\(\displaystyle THUS\ (k + 1)^2 < 4^{(k+1)}.\)

So step 2 is proved. The whole row of dominoes has fallen. And we can say

\(\displaystyle For\ any\ integer\ n \ge 1, n^2 < 4^n.\)

You need to understand why this type of proof works. The mechanics involve manipulating the proposition for k + 1 to relate it to the proposition for k and using the fact that k is greater than or equal to 1.

Does this help? Tell me at any step where things get hazy.

 

[mperez2k]

Let's talk intuitively first about the proof of propositions by weak mathematical induction.

It works this way: first you prove that a proposition about the positive integers is true for 1. Second you prove that if it is true for any integer k not less than 1, it is also true for (k + 1).

So because it is true for 1 (by the first step), it is also true for 2 (by the second step), but that means (again by the second step) that it is true for 3, which entails that the second step makes it true for 4, which means it is valid for 5, and so on forever. The whole row of dominoes falls. Very intuitive, very simple.

More formally, you prove the proposition true for 1, which you did. That is step 1 in every proof by mathematical induction.

Step 2 is harder. You consider ANY integer k that is NOT less than 1 for which the proposition is true. You KNOW that at least one such integer exists because you proved that ONE was such an integer earlier. However, you must NOT assume that k = 1 because, to make the dominoes fall, it must be true for ever bigger integers.

\(\displaystyle STEP\ 1:\ 1^2 = 1 < 4 = 4^1 \implies n^2 < 4^n\ if\ n\ is\ an\ integer = 1.\)

\(\displaystyle STEP\ 2:\ Let\ k\ be\ any\ integer\ such\ that\ k \ge 1\ and\ k^2 < 4^k.\)

There is at least one such integer, namely 1, but you are NOT assuming that k = 1. This is key to the logic.

\(\displaystyle 4^{(k+1)} = 4 * 4^k.\) I am going to try to reduce the terms of the proposition for k + 1 to k and KNOWN integers.

\(\displaystyle And\ (k + 1)^2 = k^2 + 2k + 1.\) Clear so far?

Now if I could prove that \(\displaystyle k^2 + 2k + 1 < 4 * 4^k,\) I have the required proof.

\(\displaystyle 1 \le k \implies 1^2 \le k^2 \implies 1 \le k^2.\)

\(\displaystyle 1 \le k \implies (2k * 1) \le (2k * k) \implies 2k \le 2k^2.\)

\(\displaystyle So\ k^2 + 2k + 1 \le k^2 + 2k^2 + k^2 = 4k^2.\)

\(\displaystyle But\ 4k^2 < 4 * 4^k.\)

\(\displaystyle So\ k^2 + 2k + 1 < 4 * 4^k.\)

\(\displaystyle THUS\ (k + 1)^2 < 4^{(k+1)}.\)

So step 2 is proved. The whole row of dominoes has fallen. And we can say

\(\displaystyle For\ any\ integer\ n \ge 1, n^2 < 4^n.\)

You need to understand why this type of proof works. The mechanics involve manipulating the proposition for k + 1 to relate it to the proposition for k and using the fact that k is greater than or equal to 1.

Does this help? Tell me at any step where things get hazy.

WOW! This is the one I am looking for. A well-detailed explanation. I thank you for this. Really, thank you.

I have a question if you don't mind. Are there another easy steps on how to prove k² + 2k + 1<4*4^k ?
Or if none, I really need to do the thing you did. I would think of 2 equations, which when added, I would get the Left Hand Side?
Is it always the Left Hand Side which is needed to be shown up first? Then, I would go to the first inequality, by substitution, I could bridge the 2 different inequalities. Is it that?

 

[Deleted member 4993]

I have a question. For what is the (2n)² > (n+1)² ?
Where did you get the (n+1)? I am a bit confused with it.
Sorry, i really can't see your solution properly. Thank you.

Lets use k here

Our goal was to show that 4^k+1 > (k+1)²

We have shown that:

4^k+1 > (2k)² if we assume that for some k we have 4^k > k²

Now we know that (2k)² > (k+1)² for all k>1 (because 2k > k+1)

Thus for all k>1

4^k+1 > (2k)² > (k+1)² for all k>1 → 4^k+1 > (k+1)²

 

[JeffM]

WOW! This is the one I am looking for. A well-detailed explanation. I thank you for this. Really, thank you.

I have a question if you don't mind. Are there another easy steps on how to prove k² + 2k + 1<4*4^k ?
Or if none, I really need to do the thing you did. I would think of 2 equations, which when added, I would get the Left Hand Side?
Is it always the Left Hand Side which is needed to be shown up first? Then, I would go to the first inequality, by substitution, I could bridge the 2 different inequalities. Is it that?

The concept behind proofs by weak mathematical induction is easy: you arrange the whole row of dominoes so they knock each other down one after another. Once you get that concept, the structure of the proof becomes obvious. And usually the proof of the first step is fairly obvious as well. The proof for the second step can be very difficult to find. I do not think that it is possible to give a concrete general rule for finding the proof for the second step.

When the proposition involves an equation or inequation, my approach is to restate both the left hand side and the right hand side for k + 1 in terms of k. Then I remind myself of what I need to prove. I doubt it ever makes any difference which side you work on first. I am very lazy so I pick whatever seems simpler. However, the proof will invariably take advantage of the fact that k is positive integer and that the proposition to be proved generally is true for k specifically. So that gives you clues to finding a proof. I am sorry I cannot be more specific; finding proofs is a creative process that is not mechanical.

So you must not think that you can copy this proof for other propositions. I found a way that worked for this case, but it is likely to be useless for others. What you can take from this exercise is the general structure, not a detailed template. Try some other problems and come here for help.denis says that there are three ways to learn math: practice, practice, and practice.

 

[lookagain]

My problem is about induction.

n² < 4ⁿ for n belonging to the set of natural numbers

It is sufficient at the start to show by induction that \(\displaystyle n < 2^n, \ \ for \ \ n \ \ a \ \ natural \ \ number.\)

Then, because the bases and exponents are positive integers,


\(\displaystyle n < 2^n \ \ \implies\)

\(\displaystyle (n)^2 < (2^n)^2 \ \ \implies\)

\(\displaystyle n^2 < 2^{2n} \ \ \implies \)

\(\displaystyle n^2 < (2^2)^n \ \ \implies\)

\(\displaystyle n^2 < 4^n \)


- - - - - - - - - - - - - - - - - - - - - - - - - - - - -


The same can be said to be true for proving by induction that

\(\displaystyle n^3 < 8^n, \ \ n^4 < 16^n, \ \ and \ \ so \ \ on, \ \ for \ \ n \ \ belonging \ \ to \ \ the \ \ set \ \ of \ \ natural \ \ numbers.\)