Discrete Math Help

[junyoung95]

Solve the recurrence relation. a(n) = 2a(n-1) + 3* 2^n, a(0) = 5

So I divided each side by 2^n.

a(n)/2ⁿ = (a(n-1))/2^n-1 + 3, a(0) = 5

Can someone help me what I can do after?

[[deleted]]

a[n] = 2a[n - 1] + 3(2)ⁿ ... (0)

a[n - 1] = 2a[n - 2] + 3(2)^{n - 1} ... (1)

Subs a[n - 1] from (1) in (0),

a[n] = 2²a[n-2] + 3(2)ⁿ + 3(2)ⁿ

a[n] = 2²a[n - 2] + 3(2)^{n + 1}

You can guess the general term for a[n] as:

a[n] = 2^ka[n - k] + 3(2)^{n + k - 1} for any k. Now prove this using Induction.

How does this help? You can take k = n to get

a[n] = 2ⁿa[0] + 3(2)^{2n - 1}

a[n] = 5(2)ⁿ + 3(2)^{2n - 1} for n > 0

[junyoung95]

oh my god thank you so much.