Harder Meth Induction (1 Viewer)

[.ben]

This question is hard beware:

Given U_n=4U_n-1-5U_n-2+2U_n-3 together with U₁=3, U₂=1, and U₃=0, prove that U_n=2^n-1-3n+5 for n=1, 2, 3 .....

For the algebra in this one, do you assume for n=k, n=k+1, and n=k+2 and prove for n=k+3 or assume for just n=k and n=k+1 and prove for n=k+2?

Thanks

 

[vafa]

what does that mean by 2u^n-1, ok how would you show u2=3 because u2=2u-6+5

 

[haque]

Do u want the solution or just how to go about it? usually we assume it's true for n<=k so all numbers leading up to k since this is a recurrence relation-however u can simply assume true for the terms involved in the next term to be considered-consult cambridge 4 u for more details.

 

[haque]

No it's actually U except the n-1 is a subscript rather than a power-i mean it works but only for n greater than or equal to 3

 

[haque]

I never said u were wrong or anything-i'm just saying that it seems to work for U as well although there is a restriciton on the starting value of n-besides the fact that u do maths at uni doesn't mean u should be arrogant about it-if i can gert my hands on some those specific uni books and tutorials i'll make sure i learn it.

 

[Riviet]

Using Iruka's contribution,

We assume:

* U_k=2^k-1 - 3k + 5

* U_k-1=2^k-2 - 3k + 8

* U_k-2=2^k-3 - 3k + 11

We are required to prove that

U_k+1=2^k - 3k + 2

U_k+1=4U_k - 5U_k-1 + 2U_k-2
=4(2^k-1 - 3k + 5) - 5(2^k-2 - 3k + 8) + 2(2^k-3 - 3k + 11)
=20 + 2.2^k - 12k -5.2^k-2 + 15k -40 + 2^k-2 - 6k + 22
=2.2^k - 4.2^k-2 - 3k + 2
=2.2^k - 2^k - 3k + 2
=2^k -3k + 2, as required.

 

[vafa]

Do you know how to solve a recurrence relation using the method of undetermined coefficients? Applying it to this problem, I get

U<SUB>n</SUB> = 5+ 2<SUP>n-1</SUP> - 3n

So I think the capital U in the original question is a typo.

You are right because otherwise that would not make any sense.

solution:
View attachment 13882

 

[.ben]

Yea sory guys, i mistttypped it.

Anyway i get it now thx vafa and riviet and haque and iruka and but is this the 'genera' method' of doin induction? are there any ohter 'general method' or tips and tricks?

 

[Riviet]

are there any ohter 'general method' or tips and tricks?

Quite often the induction follows some question asking to prove an identity or inequality, and this may be (and most of the time it is) useful for the induction question.