Question

Define the following function f(n) = 5^{(2^n)-(2^(n-1))}, n ≥ 1. Write a recursive definition for the function f(n)?
Consider the following recurrence: a_n= 2a_n-1 + 3 (where a₁ = 1). Compute the values of a_n for n ≤ 5. Find a solution for the recurrence definition and validate its correctness.
Consider the following recurrence: a_n=2a_n-1 +a_n-1a_n-2 (where a1 = 1). Compute the values of an for n ≤ 5.

Answer 1

Solution 1

Note that 2ⁿ = 2^n-1 + 2^n-1

f(n) = 5^{(2^n)-(2^(n-1))}

= 5^{(2^(n-1))}

f(n) = 5^{(2^(n-1))}

f(n-1) = 5^{(2^(n-2))}

f(n) = 5^{(2^(n-1))}  = 5^{(2^(n-2))} * 5^{(2^(n-2))} =f(n-1) * f(n-1)

Result:

f(n) = f(n-1) * f(n-1)

To verify our result note that:

f(1) = 5^{2 - 1} = 5¹

f(2) = 5^{4 - 2} = 5² = f(1) * f(1)

f(3) = 5^{8 - 4} = 5⁴ = f(2) * f(2)

f(4) = 5^{16 - 8} = 5⁸ = f(3) * f(3)

f(5) = 5^{32 - 16} = 5¹⁶ = f(4) * f(4)

Solution 2

a_n= 2a_n-1 + 3 (where a₁ = 1)

a₂= 2a₁ + 3 = 2 * 1 + 3 = 5

a₃= 2a₂ + 3 = 2 * 5 + 3 = 13

a₄= 2a₃ + 3 = 2 * 13 + 3 = 29

a₅= 2a₄ + 3 = 2 * 29 + 3 = 61

Note that a_n= 2ⁿ⁺¹ - 3

So  a₁ = 2² - 3 = 4 -3 = 1

  a₂ = 2³ - 3 = 8 -3 = 5

a₃= 2⁴ - 3 = 16 -3 = 13

a₄ = 2⁵ - 3 = 32 -3 = 29

a₅ = 2⁶ - 3 = 64 -3 = 61

Result

a_n= 2ⁿ⁺¹ - 3

Solution 3

a_n=2a_n-1 +a_n-1a_n-2 (where a1 = 1)

a₂ = 2a₁ +a₁a₀ = 2*1 + 1*0 = 2

a₃=2a₂ +a₂a₁ = 2*2 + 2*1 = 4+2 = 6

a₄=2a₃ +a₃a₂ = 2*6 + 6*2 = 12+12 = 24

a₅=2a₄ +a₄a₃ = 2*24 + 24*6 = 48+144 = 192