2
$\begingroup$

I'm taking an online course and help is hard to find. This specific problem has to do with recurrence relation. I apologize for being too general but I'm just looking for help in how to go about solving this problem.

The entire problem is:

Let $d_0,d_1,d_2,\ldots$ be defined by the formula $d_n=3^n-2^n$ for all integers $n\ge0$. Show that this sequence satisfies the recurrence relation: $d_k=5d_{k-1}-6d_{k-2}$.

The step I can do without any trouble is finding the statements that represent the values we're dealing with in the relation, $d_{k-1}$ and $d_{k-2}$:

$d_k=3^k-2^k$

$d_{k-1}=3^{k-1}-2^{k-1}$

$d_{k-2}=3^{k-2}-2^{k-2}$

However, when it comes time to plugging that into the relation and simplifying it down to the original definition of $d_k=3^k-2^k$ I fail miserably.

$d_k=5d_{k-1}-6d_{k-2}$

$=5\left(3^{k-1}-2^{k-1}\right)-6\left(3^{k-2}-2^{k-2}\right)$

$=5\cdot3^{k-1}-5\cdot2^{k-1}-6\cdot3^{k-2}+6\cdot2^{k-2}$

$=5\cdot\frac{3^k}{3}-6\cdot\frac{3^k}{3^2}-5\cdot\frac{2^k}{2}+6\cdot\frac{2^k}{2^2}$

Is that a decent start? Is there a better way to go, like breaking everything down into their simplest components, like so:

$d_k=5d_{k-1}-6d_{k-2}$

$=(2+3)\left(3^{k-1}-2^{k-1}\right)-(2\cdot3)\left(3^{k-2}-2^{k-2}\right)$

$=2\cdot\frac{3^k}{3}-2\cdot\frac{2^k}{2}+3\cdot\frac{3^k}{3}-3\cdot\frac{2^k}{2}-\left(\left(2\cdot\frac{3^k}{3^2}-2\cdot\frac{2^k}{2^2}\right)-\left(3\cdot\frac{3^k}{3^2}-3\cdot\frac{2^k}{2^2}\right)\right)$

But then what?

If I go either of these routes, I get stuck. I feel I have two issues: a.) identifying the way to go that seem the most logical; and, b.) working towards a solution. I don't know if I missed a big chunk in Algebra or if my brain just doesn't see what's going on.

What am I missing? Are either of these steps valid things to try? What are some general rules to follow to work these out?

Also, what specific discipline of Algebra is this? I don't think my course is introducing us to this stuff. I think it assumes we already know how to work these out.

$\endgroup$
  • $\begingroup$ Have you tried to factor $3^{k}$ and $2^{k}$? $\endgroup$ – IEDC PHY Nov 3 '18 at 0:15
  • $\begingroup$ While I appreciate your comment, I wasn't sure which line above to attempt to factor them out. $\endgroup$ – harperville Nov 3 '18 at 1:16
2
$\begingroup$

I start from what you wrote down: $$5d_{k-1}-6d_{k-2}=5\cdot3^{k-1}-6\cdot3^{k-2}-5\cdot2^{k-1}+6\cdot2^{k-2}$$ and I want to get to $d_k=3^k-2^k$.

I rewrite $3^{k-1}=3\cdot3^{k-2}$, and similarly for $2^{k-1}$: $$5\cdot3\cdot3^{k-2}-6\cdot3^{k-2}-5\cdot2\cdot2^{k-2}+6\cdot2^{k-2}$$ $$=15\cdot3^{k-2}-6\cdot3^{k-2}-10\cdot2^{k-2}+6\cdot2^{k-2}$$ I collect $3^{k-2}$ and $2^{k-2}$: $$=(15-6)3^{k-2}-(10-6)2^{k-2}=9\cdot3^{k-2}-4\cdot2^{k-2}=3^2\cdot3^{k-2}-2^2\cdot2^{k-2}$$ From here I collapse the exponents to get the desired result. $$=3^k-2^k$$

$\endgroup$
  • $\begingroup$ Well, I'm not sure what to say. I can work it out line by line with you and it makes sense as I go but I can't see where to begin on my own. What discipline is this? How can I learn more about how to solve these? Is this discrete mathematics or is discrete mathematics assuming I already know this? I've been following along in the book and it seems to have just dumped these in my lap. $\endgroup$ – harperville Nov 3 '18 at 1:27
  • $\begingroup$ @harperville This is just algebra, not discrete mathematics. $\endgroup$ – Parcly Taxel Nov 3 '18 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.