Suppose a1, a2, ... is a sequence of numbers defined recursively as follows: a1

Question

Suppose a1, a2, ... is a sequence of numbers defined recursively as follows: a1 = 1, a2 =2 and a3 = 3 and for n >= 4, an = an-1 + an-2 + 2an-3. Show that an <= 2^(n-1) for all positive integers n.

NOTE: The "n" letter is a subscript to a.

From what I understand I would use a Strong Induction Method on this question.

Here is what I did:

- Proved for n = 1 and for n = 2 and for n = 3. Since it is Strong Induction I am under the impression I prove more than one base case.

- Assumed it worked for P(k)

Essentially my problem lies with P(k+1), I'm not quite sure what I should do nor how to start.

Explanation / Answer

How did you get this: A(K+1) =A(K) +[A(K-1)+2A(K-2)] = A(K)+[A(K-1)+A(K-2)+2A(K-3)]-[ 2A(K-3)-A(K-2)] A(K+1)=A(K)+A(K) - [2A(K-3)-A(K-2)] = 2A(K) - [2A(K-3)-A(K-2)] Everything else is clear i just want to make sure i understand everything ===========THE CLARIFICATION IS GIVEN BELOW AT EVERY STEP....============  A(K+1) =A(K) +[A(K-1)+2A(K-2)]........USING THE GIVEN  DEFINITION FOR THE RECURRENCE RELATION OF A(K+1)... = A(K)+[A(K-1)+A(K-2)+2A(K-3)]-[2A(K-3)-A(K-2)].......SPLITTED THE 2*A(K-2) IN TO A(K-2)+A(K-2)...

AND ..ADDED AND SUBTRACTED 2*A(K-3)........

A(K+1)=A(K)+A(K) - [2A(K-3)-A(K-2)]...USING THE GIVEN  DEFINITION FOR THE RECURRENCE RELATION OF A(K) = 2A(K) - [2A(K-3)-A(K-2)]......BY ADDITION Everything else is clear i just want to make sure i understand everything

OK...???

 

Question Details Suppose a1, a2, ... is a sequence of numbers defined recursively as follows: a1 = 1, a2 =2 and a3 = 3 and for n >= 4, an = an-1 + an-2 + 2an-3. Show that an <= 2^(n-1) for all positive integers n.

NOTE: The "n" letter is a subscript to a.

From what I understand I would use a Strong Induction Method on this question.

Here is what I did:

- Proved for n = 1 and for n = 2 and for n = 3. Since it is Strong Induction I am under the impression I prove more than one base case.

NO HERE BASE CASE STARTS WITH N=4 ...SINCE OTHERS ARE ALL INITIAL VALUES NOT BASED ON FORMULA ....SO JUST CHECK FOR N=4...WE GET A4=A3+A2+2A1=3+2+2=7 < 2^(4-1)=2^3=8.....OK - Assumed it worked for P(k)...OK
SO WE HAVE A(K)=A(K-1)+A(K-2)+2A(K-3)<2^(K-1) A(K) < 2^(K-1) ...............................1 WHERE P>0 Essentially my problem lies with P(k+1), I'm not quite sure what I should do nor how to start. FIRSTLY WE NOTE THAT THIS IS AN INCREASING SEQUENCE OF POSITIVE NUMBERS...THAT IS .... 0<...........A(K-3) WE HAVE TPT A(K+1)=A(K)+A(K-1)+2A(K-2)<2^(K+1-1)=2^K A(K+1) =A(K) +[A(K-1)+2A(K-2)] = A(K)+[A(K-1)+A(K-2)+2A(K-3)]-[2A(K-3)-A(K-2)] A(K+1)=A(K)+A(K) - [2A(K-3)-A(K-2)] = 2A(K) - [2A(K-3)-A(K-2)] USING EQN.1... A(K+1) < 2*[2^(K-1)]-[2A(K-3)-A(K-2)]

A(K+1) < 2^K - [2A(K-3)-A(K-2)]

SINCE WE HAVE THE ASSUMPTION OF THE TRUTH OF THE STATEMENT FOR N UP TO K [SAY N UP TO K=4 AS WE HAVE ALREADY PROVED...]  AND THE FACT THAT THIS IS AN INCREASING SEQUENCE ,  WE GET

A(K+1) <2^K - P WHERE 

P =[2A(K-3)-A(K-2)] > 0

HENCE A(K+1) < 2^K ...PROVED...

NEXT IS SIMPLE WRITE UP ...OK.....

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.