Discrete Mathematics question 10 n 2 page 1 Hint 16 Example

Discrete Mathematics

question 10

n 2. page 1. Hint. 16 Example 3 on Use 10. Consider the sequence s where so 2, si and s for (a) Calculate sn for n 2, 3, 4, 5, and 6. (b) Give an explicit formula for sn (c) Check your answers in part (a) using the formula obtained in part (b) 11. in each of the following cases uive an explicit formul

Solution

Given that

s_n = s_n-1 + s_n-2 for n 2 and s₀ = 2 , s₁ = 1

a ) n = 2

s_n = s_n-1 + s_n-2

   s₂ = s_2-1 + s_2-2

s₂ = s₁ + s₀

s₂ = 1 + 2

s₂ = 3

For n = 3

s_n = s_n-1 + s_n-2

   s₃ = s_3-1 + s_3-2

s₃ = s₂ + s₁

s₃ = 3 + 1

s₃ = 4

For n=4

s_n = s_n-1 + s_n-2

   s₄ = s_4-1 + s_4-2

s₄ = s₃ + s₂

s₄ = 4 + 3

s₄ = 7

For n=5

s_n = s_n-1 + s_n-2

   s₅ = s_5-1 + s_5-2

s₅ = s₄ + s₃

s₅ = 7 + 4

s₅ = 11

For n = 6

s_n = s_n-1 + s_n-2

   s₆ = s_6-1 + s_6-2

s₆ = s₅ + s₄

s₆ = 11 + 7

s₆ = 18

b ) The given recurrence relation has the same characteristic equation, and the same roots, as the FIB sequence

Hence ,

The roots are , r₁ = (1 + 5) / 2 , r₂ = (1 - 5) / 2

r₁ – r₂ = (1 + 5) / 2 - (1 - 5) / 2

= ( 1 - 1 + 5 + 5 )/2

= 25/2

= 5

1–2r₂ = 1 - 2 ( (1 - 5) / 2)

= 1 - 1 + 5

= 5

1–2r₁ = 1 - 2 ( (1 +5) / 2)

  = 1 - 1 - 5

= -5

We solve the basis equations c₁ + c₂ = 2 and c₁r₁ + c₂r₂ = 1 to get the symmetric pair of solutions

c₁ = ( 1-2r₂) /(r₁-r₂) , c₂ = (1-2r₁)/(r₂-r₁)

c₁ = 5 / 5 , c₂ = -5 / -5

c₁ = 1 , c₂ = 1

Hence,

  Hence s_n = (r₁ )ⁿ + (r₂ )ⁿ for all n.

Therefore,

An explicit formula for s_n is , s_n = (r₁ )ⁿ + (r₂ )ⁿ for all n

c ) n = 2 , 3 , 4 , 5 , 6

  s_n = (r₁ )ⁿ + (r₂ )ⁿ , where  r₁ = (1 + 5) / 2 , r₂ = (1 - 5) / 2

   s₂ = ((1 + 5) / 2  )² + ((1 - 5) / 2 )²

   s₂ = ( 1 + (5)² + 25.1 )/4 + ( 1 + (5)² - 25.1 )/4 [since , ( a+b)² = a² + b² + 2ab , ( a-b)² = a² + b² - 2ab ]

s₂ = ( 1 + 5 +  25 ) / 4 + ( 1 + 5 - 25 ) / 4

s₂ = ( 1 + 5 +  25 + 1 + 5 -  25 ) / 4

s₂ = 12 / 4

s₂ = 3