Year 12s: what will be the first way you research your future options? >>

Proof by induction

Hello,

Please could you check if my method is correct?

A sequence is defined by the recurrence relation

u_{n+1}=-\frac{5}{u_n}+6

with u1 = 2

Prove by induction that for any natural number n,

1<u_n<5

Step 1: Check for n=1. We know that u1=2, so 1<u1<5

Step 2: Assume that the inequality holds for all natural n.

Step 3: Check for n+1.
We have

u_{n+1}=-\frac{5}{u_n}+6

If we sub. un for 1, we get

u_{n+1}=-\frac{5}{1}+6 =1

If we sub. un for 5, we get

u_{n+1}=-\frac{5}{5}+6 =5

Since we had assumed that 1<un<5, we conclude that 1<Un+1<5.

We have shown that the inequality holds for n+1 and thus it holds for all natural n.

Any clarification is much appreciated.

(edited 9 years ago)

Reply 1

ztibor

Original post by razzor

Hello,

Please could you check if my method is correct?

A sequence is defined by the recurrence relation

u_{n+1}=-\frac{5}{u_n}+6

with u1 = 2

Prove by induction that for any natural number n,

1<u_n<5

Step 1: Check for n=1. We know that u1=2, so 1<u1<5

Step 2: Assume that the inequality holds for all natural n.

Step 3: Check for n+1.
We have

u_{n+1}=-\frac{5}{u_n}+6

If we sub. un for 1, we get

u_{n+1}=-\frac{5}{1}+6 =1

If we sub. un for 5, we get

u_{n+1}=-\frac{5}{5}+6 =5

Since we had assumed that 1<un<5, we conclude that 1<Un+1<5.

We have shown that the inequality holds for n+1 and thus it holds for all natural n.

Any clarification is much appreciated.

THat is correct but I should check for n=2 because n=1 -> u1 is only a given initial value. We can get for n=2 ->u2 a calculated value through the recurrent relation.

Reply 2

razzor

Thanks a lot for your speedy reply :smile:

Reply 3

davros

Original post by razzor

Hello,

Please could you check if my method is correct?

A sequence is defined by the recurrence relation

u_{n+1}=-\frac{5}{u_n}+6

with u1 = 2

Prove by induction that for any natural number n,

1<u_n<5

Step 1: Check for n=1. We know that u1=2, so 1<u1<5

Step 2: Assume that the inequality holds for all natural n.

Step 3: Check for n+1.
We have

u_{n+1}=-\frac{5}{u_n}+6

If we sub. un for 1, we get

u_{n+1}=-\frac{5}{1}+6 =1

If we sub. un for 5, we get

u_{n+1}=-\frac{5}{5}+6 =5

Since we had assumed that 1<un<5, we conclude that 1<Un+1<5.

We have shown that the inequality holds for n+1 and thus it holds for all natural n.

Any clarification is much appreciated.

Unfortunately you haven't proved it at all.

You've shown that 1 and 5 map to 1 and 5, but you haven't shown that for some value between 1 and 5 you couldn't output a value that goes outside that range, which is what the question is asking you to do!

Also: just noticed for Step 2 you've said "assume inequality holds for all natural numbers n". That is NOT how you set up the induction hypothesis! You should be saying "assume the inequality holds for a given natural number k". Your task is then to show that it holds for k+1 (that's what you've actually tried to do, but your wording is incorrect and you shouldn't use 'n' because 'n' refers to the general term).

Reply 4

DFranklin

Original post by razzor

Hello,

Please could you check if my method is correct?

A sequence is defined by the recurrence relation

u_{n+1}=-\frac{5}{u_n}+6

with u1 = 2

Prove by induction that for any natural number n,

1<u_n<5

Step 1: Check for n=1. We know that u1=2, so 1<u1<5

Step 2: Assume that the inequality holds for all natural n.

Step 3: Check for n+1.
We have

u_{n+1}=-\frac{5}{u_n}+6

If we sub. un for 1, we get

u_{n+1}=-\frac{5}{1}+6 =1

If we sub. un for 5, we get

u_{n+1}=-\frac{5}{5}+6 =5

Since we had assumed that 1<un<5, we conclude that 1<Un+1<5.This isn't valid reasoning: substituting two values for u_n (without any extra argument) doesn't prove anything about the behaviour for u_n between 1 and 5.

Your argument should look more like:

Since u_n < 5, we know that 5/u_n is ..., and so -5/u_n + 6 is ...
Since u_n > 1, we know that 5/u_n is ..., and so -5/u_n + 6 is ...

We conclude that