This discussion is now closed.

Check out other Related discussions

Proof by Induction FP1 basic question on method

Hi guys, I don't know why but for some reason I'm confused by something, I know this is probably really obvious but it hasn't hit me which is annoying.

Basically so I get first we do n=1, then we assume true for n=k but when we do n=k+1 I understand why we do the summation for n=k but why is that plus k + 1, I keep wanting to think it should be + 1, I know it isn't, but I was wondering if somebody could just clear up my misunderstanding.

Reply 1

Ateo

9

Original post by alygirl

...

The basic principle of mathematical induction is that you want to prove something for an integer greater or equal to a particular integer (usually 1). Essentially, you assume that some proposition is true for some integer k (ie n=k). From this you want to show that the proposition is true for the next integer (ie n=k+1). Then you prove that the proposition is true for n=1, but it follows from the previous result that it is also true for 2, then 3, etc. Thus true for all integer n greater or equal to 1.

In other cases you can also, for example, prove a result for all positive even numbers. Its just some slightly different manipulation but I won't go into that, hopefully what I've written above clarifies the idea for you :smile:

.

(edited 10 years ago)

Reply 2

Felix Felicis

13

Original post by alygirl

Hi guys, I don't know why but for some reason I'm confused by something, I know this is probably really obvious but it hasn't hit me which is annoying.

Basically so I get first we do n=1, then we assume true for n=k but when we do n=k+1 I understand why we do the summation for n=k but why is that plus k + 1, I keep wanting to think it should be + 1, I know it isn't, but I was wondering if somebody could just clear up my misunderstanding.

I think I get what you're asking, I'll run through an example.

Ok, we want to prove by induction that

\displaystyle \sum_{r=1}^{n} = \frac{1}{2} n(n+1)

for all natural n (that is the sum of the first n natural numbers.)

Ok, so for our basis case, we show it's true for n = 1

LHS

\displaystyle \sum_{r=1}^{1} 1 = 1

RHS

\displaystyle \frac{1}{2} 1 \cdot (1 + 1) = \frac{1}{2} \cdot 2 = 1

So LHS = RHS thus it is true for n = 1

Now we assume it is true for n = k:

\displaystyle \sum_{r=1}^{k} r = \frac{1}{2} k(k+1)

Now we consider n = k + 1

\displaystyle \sum_{r=1}^{k+1} r = \frac{1}{2} (k+1) (k+2)

Now...by the principle of mathematical induction, we want to assume that it is true for some arbitrary integer 'k' and we want to show that it is true for k+1 (i.e. the next integer along) if we assume it is true for k. This works because you've shown it is true for a basis case (i.e. n = 1). If we can show it is true for some arbitrary integer k + 1 if true for some arbitrary integer k and if we've shown it's true for n = 1 then it's true for n = 2. But if it's true for n = 2 then by the inductive step it's true for n = 3. And if it's true for n = 3 ... and so on.

So, by assumption,

\displaystyle \sum_{r=1}^{k} r = \frac{1}{2} k(k+1)

Now, consider what

\displaystyle \sum_{r=1}^{k+1} r

means. This is basically the same thing as:

\displaystyle \sum_{r=1}^{k+1} r = \underbrace{1 + 2 + 3 + 4 + ... + (k-2) + (k-1) + k}_{*} + (k+1)

But we've assumed that

(*)

(that is

1 + 2 + 3 + 4 + ... + (k-1) + k = \displaystyle\sum_{r=1}^{k}

is equal to:

\dfrac{1}{2} k(k+1)

from our inductive hypothesis. So we can write it as:

\displaystyle \sum_{r=1}^{k+1} = \frac{1}{2} k (k+1) + (k+1)

If we factorise out k+1, we get:

\displaystyle (k+1) \left( \frac{1}{2} k + 1 \right) = (k+1) \left ( \frac{k + 2}{2} \right) = \frac{1}{2} (k+1) (k+2)

as required.

So, the proposition is true for n = k + 1 if true for n = k. As it is true for n = 1, it is true for all natural n by the principle of mathematical induction.

Hope that made sense :colondollar:

(edited 10 years ago)

Reply 3

EBayton

Hey just wondering if you could help with a particular proof by induction problem? I can do the textbook exercises but the exams stuff is sending my crazy, I've looked at the mark scheme and they use a method which goes like
to prove (k+1) you do f(k+1)-f(k) which I do not get at all, that's not how we were taught it :L

This is the problem I'm stuck on...

use induction to prove that, for all positive integers n,
f(n) = (2n+1)(7^n) -1 is divisible by 4.

Been trying for a good 45 minutes now, so confused hahaha, any help would be great :smile:

Reply 4

Farhan.Hanif93

18

Original post by EBayton

Hey just wondering if you could help with a particular proof by induction problem? I can do the textbook exercises but the exams stuff is sending my crazy, I've looked at the mark scheme and they use a method which goes like
to prove (k+1) you do f(k+1)-f(k) which I do not get at all, that's not how we were taught it :L

This is the problem I'm stuck on...

use induction to prove that, for all positive integers n,
f(n) = (2n+1)(7^n) -1 is divisible by 4.

Been trying for a good 45 minutes now, so confused hahaha, any help would be great :smile: