Math Help - proof by induction

1. proof by induction

sorry, not sure which subforum this should go to.

Sequence u1, u2, u3,... is know to converge to the limit m and is such that $u_{n+1}=\frac{9u_n+3}{u_n+7}$

a) find the value of m.
b) it is given that $u_n=1$. by first writing $u_n$ in terms of $u_{n+1}$, and considering $3-u_n$, prove by induction that $u_n<3$ for all positive integers n.

for a.

i substitute m, giving $m=\frac{9m+3}{m+7}$
solving this gives $m=-1,3$
how do i immediately know whether it is -1 or 3 that it converges to? i know i can draw a graph of $u_{n+1}$ against $u_n$, and draw a line of y=x, and based on the gradient of the curve determine which it converges to. but i believe im not supposed to do that, this topic is only induction. and also this is a short question which probably carries very little marks. there must be some direct and quick way to immediately see which it converges to?

for b.
i proved that it is valid for n=1.
i assumed that it is valid for n=k.
that gives $u_k<3$
expressing $u_n$ in terms of $u_{n+1}$, $u_n=-\frac{7u_{n+1}-3}{u_{n+1}-9}$
considering $3-u_n$,
$3-u_n=\frac{10u_{n+1}-30}{u_{n+1}-9}$
since it is assumed $u_k<3$,
then $\frac{10u_{n+1}-30}{u_{n+1}-9}>0$
this is where my problem starts. i can't show from here that $u_{n+1}<3$
how? in fact what i get is $u_{n+1}<3,u_{n+1}>9$. theres this $u_{n+1}>9$, which shouldn't be if i were to prove this.

2. Re: proof by induction

You are aware of how this behaves?

$u_0=-1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=-1$

$u_0 \neq -1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=3$

Proving the first statement by induction should be pretty trivial.

You seem to know enough of what's going on to take a stab at proving the second statement.

3. Re: proof by induction

Consider monotonicity. It may help to waste u_{n+1}>0

4. Re: proof by induction

Originally Posted by romsek
You are aware of how this behaves?

$u_0=-1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=-1$

$u_0 \neq -1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=3$
no. what do you refer to by $u_0$?

5. Re: proof by induction

Originally Posted by muddywaters
no. what do you refer to by $u_0$?
I guess you call it $u_1$, just the first element of the sequence. It's defined recursively so you can assign anything to the initial value.

6. Re: proof by induction

Originally Posted by romsek
I guess you call it $u_1$, just the first element of the sequence. It's defined recursively so you can assign anything to the initial value.
oh k. now i understand what
$u_0=-1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=-1$

$u_0 \neq -1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=3$
says, but how do you know that it's like that?

7. Re: proof by induction

From equation for m and monotonicity of u_{n}

8. Re: proof by induction

Originally Posted by Cartesius24
From equation for m and monotonicity of u_{n}
how do u find out the monotonicity of u_n? Differentiate? With respect to what? And how will it tell me where is converges to?

9. Re: proof by induction

Originally Posted by muddywaters
how do u find out the monotonicity of u_n? Differentiate? With respect to what? And how will it tell me where is converges to?
This might help

$u_{n+1}-u_n=\frac{9u_n+3}{u_n+7}-u_n=\frac{\left(3-u_n\right)\left(u_n+1\right)}{u_n+7}$

10. Re: proof by induction

Originally Posted by romsek
You are aware of how this behaves?

$u_0=-1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=-1$

$u_0 \neq -1 \Rightarrow \displaystyle{\lim_{n \to \infty}}=3$

Proving the first statement by induction should be pretty trivial.

You seem to know enough of what's going on to take a stab at proving the second statement.
the second statement is not true

for $u_0=-3.25$ the sequence does not converge

11. Re: proof by induction

Originally Posted by Idea
This might help

$u_{n+1}-u_n=\frac{9u_n+3}{u_n+7}-u_n=\frac{\left(3-u_n\right)\left(u_n+1\right)}{u_n+7}$
Sorry, i still cant tell if it converges to 3 or -1 from that.

12. Re: proof by induction

Originally Posted by muddywaters
Sorry, i still cant tell if it converges to 3 or -1 from that.
no you can't tell convergence from this

13. Re: proof by induction

Originally Posted by Idea
no you can't tell convergence from this

How to show monotonicity???

14. Re: proof by induction

I will do this in the case where the first term in the sequence is between -1/3 and 3

$-1/3

Proof is by induction using the following

$3-u_{n+1}=\left(3-u_n\right)\frac{6}{u_n+7}$

Next use

$u_{n+1}-u_n=\frac{\left(3-u_n\right)\left(u_n+1\right)}{u_n+7}$

to show that the sequence is monotone increasing and since it is bounded above, it converges (to 3)

15. Re: proof by induction

Originally Posted by muddywaters
Sorry, i still cant tell if it converges to 3 or -1 from that.
Yes, that's the point every one has been trying to make. Just this equation can't tell you what it converges to. You need to know some starting value also.

Page 1 of 2 12 Last