How do I show that this sequence satisfies the given recurrence relation?

I have been stuck on this problem all day, so something is clearly not clicking. It's an example problem with a given solution, but I am totally lost

Let c0,c1,c2,... be defined by the formula c subscript n = 2^n - 1 for all integers n ≥ 0.

Show that this sequence satisfies the recurrence relation

b subscript k = 4b subscipt k-1

I apologize for the poor formatting

Eventually, it gets to c subscript k-1 = 2^k-1 -1 and I have no idea how

1 Answer

Relevance
  • nbsale
    Lv 6
    5 months ago
    Favorite Answer

    Problems like this are generally easy, but they can be tedious, so you have to be careful. It's also very hard to prove things that aren't true, which seems to be the case here.

    Let's standardize the notation as c(i) = the i-th term. You have things like c0 and b subscript k which might be part of your confusion.

    You want to show c(k) = 4c(k-1)

    4c(k-1) = 4(2^(k-1) -1) = [2^(k+1)] - 4 (A)

    Now 2^(k+1) = 2•2^k = 2•2^k - 2 + 2

    = 2(2^k - 1) + 2 = 2c(k) + 2

    Plug that expression for 2^(k+1) into (A)--the bracketed expressions--and you get

    4c(k-1) = [2c(k) + 2] - 4 = 2c(k) - 2

    Since that's not = c(k), the statement is not true.

    Here's a table of some values illustrating that it's not true.

    Maybe you mistyped things?

    k c(k) 4c(k-1)

    0 0

    1 1 0

    2 3 4

    3 7 12

    4 15 28

    5 31 60

    • james5 months agoReport

      I did mess up

      https://imgur.com/x8fcb9Z

Still have questions? Get your answers by asking now.