MedVision ad

Help with complex (1 Viewer)

Trebla

Administrator
Administrator
Joined
Feb 16, 2005
Messages
8,391
Gender
Male
HSC
2006
Since is a root then

Which implies

Use the same argument for and the result follows

For the strong induction step use the property that

and

and the result should follow
 

mathsbrain

Member
Joined
Jul 16, 2012
Messages
162
Gender
Male
HSC
N/A
Since is a root then

Which implies

Use the same argument for and the result follows

For the strong induction step use the property that

and

and the result should follow
is this an HSC question?
 

mathsbrain

Member
Joined
Jul 16, 2012
Messages
162
Gender
Male
HSC
N/A
also never quite understood difference between strong vs weak induction, any examples to help make sense of this?
 

fan96

617 pages
Joined
May 25, 2017
Messages
543
Location
NSW
Gender
Male
HSC
2018
Uni Grad
2024
also never quite understood difference between strong vs weak induction, any examples to help make sense of this?
Say you have a statement you're trying to prove by induction.

A normal induction proof would go like "if this statement is true for k then it must also be true for k + 1."

A strong induction proof would be more like "if this statement is true for all numbers less than or equal to k then it must also be true for k + 1."

This extra condition gives you more to work with, and you sometimes need it for harder proofs.

(You may not need to make the assumption for every single number less than k, but you would need to make the assumption for at least a few.)

I vaguely remember doing a question related to the Fibonacci numbers with strong induction - you can try to find it online.
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,642
Gender
Male
HSC
N/A
I vaguely remember doing a question related to the Fibonacci numbers with strong induction - you can try to find it online.
One such question proves Binet's formula for the nth Fibonacci number as follows:

Define F0 = 0, F1 = 1, and Fk + 2 = Fk + 1 + Fk for non-negative integers k. Use strong induction to prove that



for all non-negative integers n.

Strong induction is required as you need to assume a formula for Fk + 1 and Fk and so need to prove two consecutive values work in the first part.

An alternative proof (also requiring strong induction) is as follows:

Prove that provided x2 = x + 1, then (with the above definition of Fn) for all integers n greater than 1. From this result, derive Binet's formula.
 
Last edited:

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top