Induction question (1 Viewer)

[Giant Lobster]

For those questions asking u to prove stuff like n lines making n^2 + n + 1 regions etc (not sure if thats right but thats no matter) do u deduce a recursive relation between u_n+1 and u_n before starting the induction process? Ive always known that as the way to do those induction questions, as its required in step 3 but im not sure how other ppl do it.

(e.g. u_n+1 = u_n + n + 1 (following some reasoning on why))

 

[KeypadSDM]

I've seen something similar, but I think I may be talking about something completely different. For example, you're given:

T_n+1 = T_n + n + 1 (From your question)

Then you derive something to make it:

T_n+1 = f(n)

Where f(n) is purely in n with no T_n's at all...

 

[turtle_2468]

yes you do get a recursive relation in order to prove step 3. It'd go something like this: (this is the long, ultra-rigorous version, shorten as desired)
Observe that one line with no intersection creates 1 new region. (dividing the plane into 2) Furthermore note that for each intersection the new line has with another line, an additional region is created. Therefore the (k+1)-th line (assuming no parallel lines and thus k intersections) creates k+1 new regions. So u_(k+1)=u_k+k+1 as you wrote.

by the way, keypad, the deriving process in general is extremely hard

 

[Giant Lobster]

yes you do get a recursive relation in order to prove step 3.

Thanks but im referring to those questions where they dont give you any relation, but ask you straight out, prove u_n = f(n). In that case must I deduce a recursive relation myself before commencing induction, or is there another way?

 

[KeypadSDM]

The recursive relationship should already be given to you as it defines u_n. It may be given to you in words, but you get the words that define u_n, and change that into a recursive formula involving u_n, u_(n-1) etc.

Then you assume true for n = k
Then for n = k+1 convert the

u_(k+1) into something which uses u_k.

Then the formula can be subbed into the u_k part.

 

[KeypadSDM]

Originally posted by turtle_2468
by the way, keypad, the deriving process in general is extremely hard

But they're not going to throw a toughie at you in 4 unit. If anything they always tell you what to derive.

 

[Giant Lobster]

Is induction ever in q8 in a souped up "enhanced" form? cos all the ones ive met are all doable... hmmm

edit:
and what of the ones where you're required to conjecture a result, then prove it by induction? will they ever become tricky?