Induction

[tenshineko]

Hi everyone

I've just been working on an assignment today, and I've done most of it, but there are these few that I am having trouble tackling.
First we have to determine whether to use regular induction or strong induction (Strong has been giving me a bit of difficulty, so that may be what is tripping me up)

Thanks a lot for any help!

no more problems! i was able to work them out

 

[galactus]

2. Use induction to prove that the Fibonacci numbers F[sub:6wn5030d]n[/sub:6wn5030d] satisfy the following identity for n>=1:

F[sub:6wn5030d]1[/sub:6wn5030d]+F[sub:6wn5030d]2[/sub:6wn5030d]+F[sub:6wn5030d]3[/sub:6wn5030d]+...+F[sub:6wn5030d]n[/sub:6wn5030d]=F[sub:6wn5030d]n+2[/sub:6wn5030d]-1

This one should not be too bad.

By definition, \(\displaystyle f_{1}+f_{2}+f_{3}+...............+f_{n}=f_{n+2}-1\)

Show that \(\displaystyle \underbrace{f_{1}+f_{2}+f_{3}+................+f_{n}}_{\text{this is f(n+2)-1}}+f_{n+1}=f_{n+3}-1\)

So, we have \(\displaystyle f_{n+2}-1+f_{n+1}=f_{n+3}-1\)

By fibonacci, \(\displaystyle f_{n+1}+f_{n+2}=f_{n+3}\)

and that's it. You can touch it up and add the intricacies.

 

[DrMike]

3. Let a[sub:1wmenkmw]n[/sub:1wmenkmw] be defined by the recurrence relation

a[sub:1wmenkmw]n+1[/sub:1wmenkmw]=2a[sub:1wmenkmw]n[/sub:1wmenkmw]+a[sub:1wmenkmw]n-1[/sub:1wmenkmw] for n>=2

with initial conditions a[sub:1wmenkmw]1[/sub:1wmenkmw]=1, a[sub:1wmenkmw]2[/sub:1wmenkmw]=5. Prove that a[sub:1wmenkmw]n[/sub:1wmenkmw] is an odd number for all n >=1.

For this last one, I've started off using regular induction, showing the base case n=2 yields 11, which is odd. I have made the inductive hypothesis that a[sub:1wmenkmw]n[/sub:1wmenkmw]=2k+1 (a[sub:1wmenkmw]n[/sub:1wmenkmw] is odd) but once I try to show that a[sub:1wmenkmw]n+1[/sub:1wmenkmw] is odd, I have to worry about a[sub:1wmenkmw]n-1[/sub:1wmenkmw] which I have not assumed anything about. This makes me think that this one is supposed to use strong induction, but I really have no idea. The other two problems I have no work for, as I've just stared blankly at them for a while.

Thanks a lot for any help!

Strong induction is a special case of ordinary induction. For example, if you need to prove "P(n) for all n>0", and you find you need strong induction, just let Q(n) = "P(k) for k=1,2,...,n", then prove "Q(n) for all n>0" using ordinary induction.

 

[tenshineko]

thanks a lot for both your responses!

i was able to get the 3rd one after sitting down and trying to use/understand strong induction.

the only one i have left is the first one

I am at the point where i have shown the base cases (n=1 and n=2) hold

i have said

F[sub:2jaqm22d]n+1[/sub:2jaqm22d]=F[sub:2jaqm22d]n[/sub:2jaqm22d]+F[sub:2jaqm22d]n-1[/sub:2jaqm22d]

so now i am showing

F[sub:2jaqm22d]n[/sub:2jaqm22d]+F[sub:2jaqm22d]n-1[/sub:2jaqm22d]>= 1/sqrt(5) * (sqrt(5)/2)[sup:2jaqm22d]n+1[/sup:2jaqm22d]

From the IH, i know that F[sub:2jaqm22d]n[/sub:2jaqm22d] is at least 1/sqrt(5) * (sqrt(5)/2)[sup:2jaqm22d]n[/sup:2jaqm22d] but i do not know how to continue with the proof.

any guidance is appreciated!

 

[DrMike]

thanks a lot for both your responses!

i was able to get the 3rd one after sitting down and trying to use/understand strong induction.

the only one i have left is the first one

I am at the point where i have shown the base cases (n=1 and n=2) hold

i have said

F[sub:qtb2alaf]n+1[/sub:qtb2alaf]=F[sub:qtb2alaf]n[/sub:qtb2alaf]+F[sub:qtb2alaf]n-1[/sub:qtb2alaf]

so now i am showing

F[sub:qtb2alaf]n[/sub:qtb2alaf]+F[sub:qtb2alaf]n-1[/sub:qtb2alaf]>= 1/sqrt(5) * (sqrt(5)/2)[sup:qtb2alaf]n+1[/sup:qtb2alaf]

From the IH, i know that F[sub:qtb2alaf]n[/sub:qtb2alaf] is at least 1/sqrt(5) * (sqrt(5)/2)[sup:qtb2alaf]n[/sup:qtb2alaf] but i do not know how to continue with the proof.

any guidance is appreciated!

Instead of proving

"for all n>=2, F[sub:qtb2alaf]n[/sub:qtb2alaf] >= formula(n)",

try proving

"for all n>=2, F[sub:qtb2alaf]n[/sub:qtb2alaf] >= formula(n) AND F[sub:qtb2alaf]n-1[/sub:qtb2alaf] >= formula(n-1)"

Your base case is when n=2 : "F[sub:qtb2alaf]2[/sub:qtb2alaf] >= 1/sqrt(5)*(sqrt(5)/2)[sup:qtb2alaf]2[/sup:qtb2alaf] AND F[sub:qtb2alaf]1[/sub:qtb2alaf] >= 1/sqrt(5)*(sqrt(5)/2)[sup:qtb2alaf]1[/sup:qtb2alaf]"

Now, assuming "F[sub:qtb2alaf]n[/sub:qtb2alaf] >= formula(n) AND F[sub:qtb2alaf]n-1[/sub:qtb2alaf] >= formula(n-1)", try to prove "F[sub:qtb2alaf]n+1[/sub:qtb2alaf] >= formula(n+1) AND F[sub:qtb2alaf]n[/sub:qtb2alaf] >= formula(n)"...