Solving a Recurrence Relation Using Induction: Step-by-Step Guide

[bubblewrap]

Below I have uploaded the page I am having trouble with.

Here it says that it is using induction on n but I don't understand how it uses the formula for when n=j to derive the formula for when n=j+1

 

[Samy_A]

Below I have uploaded the page I am having trouble with.

Here it says that it is using induction on n but I don't understand how it uses the formula for when n=j to derive the formula for when n=j+1View attachment 94504

What is the definition of $y_n(t)$?
I can guess that equation (5) is $|y_n(t)-y_0| \leq M(t-t_0)$. Is this guess correct?

EDIT: ok, I found it, $y_n$ are Picard iterates.
Equation (5) is $|y_n(t)-y_0| \leq M(t-t_0)$ for $t_0 \leq t \leq t_0+\alpha$.
So by definition $y_{j+1}(t)=y_0 + \int_{t_0}^t f(s,y_j(s)) \, ds$

He uses the definition of $y_{j+1}$ and that $M$ is defined as the maximum on the rectangle defined by $t_0 \leq t \leq t_0+a,\ |y-y_0| \leq b$.
Thanks to the induction hypothesis that he knows that $|f(s,y_j(s))|\leq M$.

 

[bubblewrap]

What is the definition of $y_n(t)$?
I can guess that equation (5) is $|y_n(t)-y_0| \leq M(t-t_0)$. Is this guess correct?

EDIT: ok, I found it, $y_n$ are Picard iterates.
Equation (5) is $|y_n(t)-y_0| \leq M(t-t_0)$ for $t_0 \leq t \leq t_0+\alpha$.
So by definition $y_{j+1}(t)=y_0 + \int_{t_0}^t f(s,y_j(s)) \, ds$

He uses the definition of $y_{j+1}$ and that $M$ is defined as the maximum on the rectangle defined by $t_0 \leq t \leq t_0+a,\ |y-y_0| \leq b$.
Thanks to the induction hypothesis that he knows that $f(s,y_j(s))\leq M$.

But he didn't use n=j to show anything since $f(s,y_j(s))\leq M$ is a definition and not something deduced from n=j

 

[Samy_A]

Let's rewrite it in the correct order.
By definition, $y_{j+1}(t)=y_0 + \int_{t_0}^t f(s,y_j(s)) \, ds$.
Let R be the rectangle defined by $t_0 \leq t \leq t_0+a,\ |y-y_0| \leq b$ where $a, b$ are positive numbers.
Let $M$ be the maximum of $f$ on that rectangle.
Set $\alpha=min(a,\frac{b}{M})$.
Then $|y_n(t)-y_0| \leq M(t-t_0)$ for $t_0 \leq t \leq t_0+\alpha$. (Equation (5) in your text.)

Assume that it has been proven for $j$.
So $|y_j(t)-y_0|\leq M(t-t_0)$ for $t_0 \leq t \leq t_0+\alpha$.
But then $|y_j(t)-y_0|\leq M(t-t_0) \leq M\alpha \leq b$, meaning that $(t,y_j(t))$ lies in the rectangle R, so that $|f(t,y_j(t)| \leq M$. This is where the induction hypothesis is crucial.
That's what he uses in the last step: in the integral he just uses $|f(s,y_j(s)|\leq M$.

But he didn't use n=j to show anything since $f(s,y_j(s))\leq M$ is a definition and not something deduced from n=j

This only holds if $(s,y_j(s))$ lies in the rectangle R. He knows it does thanks to the induction hypothesis.

 

[bubblewrap]

Let's rewrite it in the correct order.
By definition, $y_{j+1}(t)=y_0 + \int_{t_0}^t f(s,y_j(s)) \, ds$.
Let R be the rectangle defined by $t_0 \leq t \leq t_0+a,\ |y-y_0| \leq b$ where $a, b$ are positive numbers.
Let $M$ be the maximum of $f$ on that rectangle.
Set $\alpha=min(a,\frac{b}{M})$.
Then $|y_n(t)-y_0| \leq M(t-t_0)$ for $t_0 \leq t \leq t_0+\alpha$. (Equation (5) in your text.)

Assume that it has been proven for $j$.
So $|y_j(t)-y_0|\leq M(t-t_0)$ for $t_0 \leq t \leq t_0+\alpha$. .
But then $|y_j(t)-y_0|\leq M(t-t_0) \leq M\alpha \leq b$, meaning that $(t,y_j(t))$ lies in the rectangle R, so that $|f(t,y_j(t)| \leq M$. This is where the induction hypothesis is crucial.
That's what he uses in the last step: in the integral he just uses $|f(s,y_j(s)|\leq M$.

Thank you for your help, one last thing, am I slow if I am not getting this?

 

[Samy_A]

Thank you for your help, one last thing, am I slow if I am not getting this?

Do you agree that we are only certain that $|f(s,y_j(s)| \leq M$ if $(s,y_j(s))$ lies in the rectangle R?

 

[bubblewrap]

Do you agree that we are only certain that $|f(s,y_j(s)| \leq M$ if $(s,y_j(s))$ lies in the rectangle R?

Rectangle R depends on the two constants a and b, and these are random numbers right? So although we are not certain about what you said it could be in that condition.

 

[Samy_A]

Rectangle R depends on the two constants a and b, and these are random numbers right? So although we are not certain about what you said it could be in that condition.

Yes, a and b are two positive constants. They define the rectangle R. M is by definition the maximum of f on that rectangle.

To use that $|f(s,y_j(s))| \leq M$, you must know that $(s,y_j(s))$ lies in the rectangle R. Do you agree so far?

 

[bubblewrap]

Yes, sorry I just had dinner. I agree so far.

 

[Samy_A]

Yes, sorry I just had dinner. I agree so far.

No reason to be sorry for having dinner.

Assume that equation (5) has been proved for j.
Now he needs to show that $(s,y_j(s))$ lies in the rectangle R if $t_0 \leq s \leq t_0+\alpha$.
Equation (5) means: $|y_j(s)-y_0| \leq M(s-t_0)$ for $t_0 \leq s \leq t_0+\alpha$.
But then $|y_j(s)-y_0| \leq M(s-t_0) \leq M\alpha \leq b$, by the definition of $\alpha$. (*)

Remember how the rectangle R was defined?
$(s,y) \in R$ if $t_0 \leq s \leq t_0+a,\ |y-y_0| \leq b$.

Now look at $(s,y_j(s))$ for $t_0 \leq s \leq t_0+\alpha$.
Obviously $t_0 \leq s \leq t_0+a$.
But, more interesting, by (*), $|y_j(s)-y_0| \leq b$.
We conclude that $(s,y_j(s)) \in R$, and then by definition of M, $|f((s,y_j(s))| \leq M$. This is what he uses in the last step of his proof. He needed the induction hypothesis to prove that $(s,y_j(s)) \in R$.

 

[bubblewrap]

Thank you it's all clear now :) Is the book not self explanatory or am I slow for not getting it in the first place? (I got it now)

 

[Samy_A]

Thank you it's all clear now :) Is the book not self explanatory or am I slow for not getting it in the first place? (I got it now)

It's the book. This point is not very difficult, but one line explaining this would have been welcome.
Now he does explain just before the proof that the lemma means that the graph of $y_n$ stays within the rectangle: