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
- nbsaleLv 68 months agoFavorite 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)
1 1 0
2 3 4
3 7 12
4 15 28
5 31 60