Question

In induction if f(n) is true, how does it make f(n+1) also true?

Answer 1

Awesome, ok so it doesn't in general but that's what you have to show; so here's what you do:

When this is true:
\[2^n > 2n\] we can show that it means this is true:
\[2^{n+1} > 2(n+1)\]

agree/disagree?

Answer 2

Yes by algebraic manipulation (which not necessarily can happen in every case of induction)

Answer 3

Yeah, you can't prove everything by induction, especially false things lol. So now what's left to convince you?

Answer 4

I think this example is too easy

Use this one.
Prove by induction that Un = 3(2/3)^n - 1 where U1 = 1 and Ur+1 = (2Ur - 1)/3

Answer 5

How about this, forget the examples for a moment and just explain to me how you think induction works.

Answer 6

In this I have obtained the equation to find out Un+1 just by using N which is 2 (2/3)^n -1 but all is left to show that how is the equation correct

Answer 7

Well I think first we make an assumption. Then we show it is true for a value. Then we make an alternate equation which is kind of recursive. Then we try to show that equation is also true. The last part is what confuses me. How can we show that equation is also true. Just by matching the values of our new formed (n+1) equation with the n equation or some algebraic proof?

Answer 8

I think I see what your problem is, it's the statement \(2^n>2n\) is used to mean two separate things. On the one hand you want to prove it's true for ALL values of n greater than 2. On the other hand the way we prove that is by looking at a specific value of n for which it's true and using that to prove that the specific case n+1 is true from that.

Try to work through the example and I'll see what you're doing.

Answer 9

Is this it? I am assuming those are like subscripts or something but I might have missed some things cause that last term could have been \(U_{r-1}\) for all I know.

Prove by induction that \(U_n = 3(2/3)^n - 1\) where \(U_1 = 1\) and \(U_{r+1} = (2U_r - 1)/3\)

Answer 10

Yes correct

Answer 11

In this I have obtained the equation to find out Un+1 just by using N which is 2 (2/3)^n -1 but all is left to show that how is the equation correct

Answer 12

In this problem you didn't have to find anything, they are telling you for a fact that:

\[U_1=1\]\[U_{r+1} = \frac{2U_r-1}{3}\]

They could have asked you, "What is \(U_n=\)?" But instead they are giving you \(U_n\) and asking you to confirm that it is the correct one.

Answer 13

So what I am supposed to do?

Answer 14

Well first off, does everything in my last post make sense?

Answer 15

Yes but I think I was able to follow because it was simple logical reasoning.

Answer 16

All you've gotta do to prove it is plug in \(U_n\) to see that it satisfies the recurrence relation, and that should feel convincing in some way too hopefully.

Answer 17

literally? But it says prove by induction

Answer 18

Do you feel like this doesn't prove it or do you feel like it's not induction?

Answer 19

Your method is to input the value of n and get the value of Un and then compare it with the value you will get with Ur+1 formula when n=r+1 right?

Answer 20

Yeah, here's what I am saying to do:

\[U_{r+1} = \frac{2U_r -1}{3}\]
Plug in \(U_n = 3(\tfrac{2}{3})^n -1\) to see if it satisfies the recurrence relation:
\[3(\tfrac{2}{3})^{r+1} -1 = \frac{2( 3(\tfrac{2}{3})^r-1) -1}{3}\]
few steps of algebra shows that they are equal.

Answer 21

I thought you were here because you didn't know what induction was, I'm here telling you what induction is; and this is part of induction lol.

Answer 22

Got it thanks

Answer 23

n = r+1 right?

Answer 24

Yeah, maybe sleep on it and come back with a fresh slate. Induction is like a row of dominos, once you understand that the \(r\)th domino knocks down the \( (r+1)\)th domino all that's left is to knock down the first one and they're all fallen over.

Answer 25

I get it there is not just one way to prove by induction right?

Answer 26

Fundamentally, no. The difference between this problem and the other problem was the information they give you was different, so you were looking at it from a different perspective.

Answer 27

Oh got it. If the equation wasn't provided of Un than we had to the whole induction proofing right?

Answer 28

@FaiqRaees


I will explain induction to you.

Imagine you have some dominoes and you set them up.

Now imagine I can show you that no matter what, if you knock down a domino behind some other domino then the later domino will fall.

But this is not enough to insure that all dominoes fall, we must first assert that the very first one falls.

This is just like induction. You want to show that if some statement is true for SOME n, then it is true for the next one.

So in your case, we assume \(2^n>2n\) for SOME n. Note that this is NOT assuming the conclusion because we are trying to show it is true for ALL \(n\) and here we are just assuming it is true for some \(n\) and of course this is true because it is easy to show for \(n=3\).

So we may assume it is true for some \(n\). (again we are not assuming it is true for all \(n\) )

So we have that there exists SOME \(n\) such that \(2^n>2n\). We now want to show that this assumption about SOME particular \(n\) will extend to the next \(n\), in other words we want to show \(2^n>2n \implies 2^{n+1}>2(n+1)\).

So

Assume \(2^n>2n\) for some \(n\), then we have

\(2^n>2n\implies 2^n*2>2n*2\) this is obviously true.

This leads to \(2^{n+1}>2n*2=4n=2n+2n>2n+2=2(n+1)\)

Thus \(2^n>2n\) for all \(n\ge 3\) as required.

This might all be easier to understand, if you use \(k\) instead of \(n\) and many people do use \(k\) for this reason. i.e. assume it is true for some \(k\in \mathbb{N}\) and then show that this implies it is true for \(k+1\).

Answer 29

yeah thanks @zzr0ck3r @Kainui Cleared it in the starting of this post

Answer 30

word*

Answer 31

@FaiqRaees Ask yourself, what were the analogous parts of this problem and the other problem? Match those things up, and you'll get closer to understanding I think.

Answer 32

Well this question was pretty straightforward. They just wanted to know if the equation would work or not. In the previous one they wanted us to prove the inequality, for all values of n

Answer 33

Side by side, the base cases were

\(2^3>2*3\) and \(U_1 =1\)

The inductive parts were:

\(2^k>2k \implies 2^{k+1} > 2(k+1)\) and \(U_{r+1} = \frac{2U_r-1}{3}\)

The statements that were proved:

\(2^n>2n\) and \(U_n = 3 (\tfrac{2}{3})^n -1\)

Answer 34

oh got it thanks.

Answer 35

Is there something you want to ask to ensure I comprehended your explanation

Answer 36

Uhh no? You said you got it, why would you lie lol.

Answer 37

Please explain how to prove that statement \(P(n)\) is true for all \(n\)?

What are the steps?

Answer 38

Start by proving the statement for starting value

Next make an equation having the input value as n+1

Now since the equation was true for n, it has to be true for n+1

Answer 39

Correct?