0

Given $$y(0)=7$$ $$y(n)=2y(n-1)+7^14^n$$ My attempt so far: $$y(n)=2y(n-1)+7^14^n$$ $$=2^2y(n-2)+2^17^14^{n-1}+7^14^n$$ $$=2^3y(n-3)+2^27^14^{n-2}+2^17^14^{n-1}+7^14^n$$ $$=2^3y(n-3)+2^27^14^{n-2}+2^17^14^{n-1}+2^07^14^n$$ $$=2^iy(i)+2^{i-1}7^14^{n-i}+\dots$$ $$=2^ny(0)+2^{n-1}7^14^{n-n}+\dots$$ $$=7*2^n+n(2^{n-1}7)$$

However, if I calculate y(1) using the given y(n), I get 42 while I get 84 using the general term I found.

Wolframalpha suggest that the answer is

$$y(n) = 2^{n - 1} (c_1 + 24 (2^n - 1))$$

Which step of my attempt is wrong ?

student
  • 668
  • The problem is most likely with those $;\cdots;$ you left out. That said, if I were to give the same suggestion twice, I would recommend you first divided by $4^n$ and solved $\cfrac{y_n}{4^n}=\cfrac{1}{2} \cdot\cfrac{y_{n-1}}{4^{n-1}}+7,$. – dxiv Dec 13 '17 at 00:16
  • @dxiv I checked back that question before writing this one. However, I am not sure what would be the next steps after dividing by $4^n$ (this is not the way we were taught in class). I am also unsure how $2y(n-1)$ divided by $4^n$ ends up being $1/2 \cdot y(n-1)/4^{n-1}$. Why isn't it $2y(n-1)/4^n$ ? My apologizes if I sound annoying. – student Dec 13 '17 at 00:51
  • $\cfrac{2 y_{n-1}}{4^n} = \cfrac{2 y_{n-1}}{4 \cdot 4^{n-1}}=\cfrac{y_{n-1}}{2 \cdot 4^{n-1}},$. Then, with $z_n=\cfrac{y_{n}}{4^n}$ you have the recurrence

    $$ z_n = \cfrac{1}{2}z_{n-1} + 7 = \cfrac{1}{2^2}z_{n-2}+\left(1 + \cfrac{1}{2}\right)\cdot 7 = \cfrac{1}{2^3}z_{n-3}+\left(1 + \cfrac{1}{2} + \cfrac{1}{2^2}\right)\cdot 7 = \cdots $$

     – dxiv Dec 13 '17 at 00:59
  • @dxiv if my understanding is correct, you are trying to transform the geometric progression into an arithmetic one? Then we could use $y(n) = t + nd$ to find the general term? Where t is y(0) and d is the constant (those are the terms in my book). The book is in french, before you ask for references. – student Dec 13 '17 at 01:18
  • $z_n = \cfrac{1}{2} z_{n-1} + 7,$ does not define an arithmetic progression, but it is an easier recurrence to "telescope" than the original one. And, once you determined $z_n,$, then you know $y_n = 4^n z_n$ of course. – dxiv Dec 13 '17 at 01:21
  • @dxiv thank you, that leads me to $2^{-n}\cdot7+7n/2$.. any chance that inspires you something I may have forgot ? This looks quite close with the answer on wolframalpha ... I'm debugging meanwhile ... – student Dec 13 '17 at 01:34
  • I ended up there using z0 = 7, if that helps. – student Dec 13 '17 at 01:45
  • 1
    With $z_0=7,$:

    $$ \begin{align} z_n &= \frac{1}{2^n} \cdot z_0+\left(1+\frac{1}{2}+\frac{1}{2^2}+\cdots+\frac{1}{2^{n-1}}\right) \cdot 7 \ &= \frac{1+2+2^2+\cdots+2^n}{2^n}\cdot 7 \ &= \frac{2^{n+1}-1}{2^n} \cdot 7 \end{align} $$

    Then $;y_n = 4^n \cdot z_n = 2^n\cdot(2^{n+1}-1)\cdot7;$ which matches the WA result.

     – dxiv Dec 13 '17 at 02:42
  • @dxiv Thank you. That definitely makes sense. However, it's still not automatic in my head how to pass from the second line to the third one. I guess I'll have a read at this tomorrow morning with a fresher mind. Feel free to wrap it up as answer if you want a 15 points (which is a small reward but still). – student Dec 13 '17 at 03:41
  • 1
    Lookup sum of geometric progression: $1+2+\cdots+2^n=\cfrac{2^{n+1}-1}{2-1},$. P.S. The actual question was which step of my attempt is wrong and that's been answered already, so I'll leave these as just comments. – dxiv Dec 13 '17 at 03:44
  • Ah! Of course! I definitely need sleep. Thank you again. – student Dec 13 '17 at 03:46

1 Answers1

1

You seem to have taken the last "dots" expression to be $$2^{n-1}7^14^{n-n}+2^{n-1}7^14^{n-n}+\cdots+2^{n-1}7^14^{n-n}\ ,$$ that is, the same term $n$ times. But it is actually $$2^{n-1}7^14^{n-n}+2^{n-2}7^14^{n-(n-1)}+2^{n-3}7^14^{n-(n-2)}+\cdots\ ,$$ which can be added up using the formula for the sum of a geometric progression.

In fact there is also an error in the previous line, $2^{i-1}7^14^{n-i}$ should be $2^{i-1}7^14^{n-(i-1)}$. If you make this correction and add up the new GP then you should get the right answer.

David
  • 82,662
  • Thank you David. I now end up with $7\cdot2^n + n(2^{n-1}\cdot7\cdot4^n)$ but this doesn't match with the answer on wolframalpha. I understand that this must be very hard for you to understand how I got there, but do you have any idea why I got there from your suggestion? – student Dec 13 '17 at 00:45
  • Do you know how to add up a GP? – David Dec 13 '17 at 00:55
  • Looks like no.. I'm googling on it – student Dec 13 '17 at 01:08
  • perhaps you have any link which explain a similar GP add up ? – student Dec 13 '17 at 02:27
  • https://www.maths.unsw.edu.au/sites/default/files/geometric-series.pdf or https://en.wikipedia.org/wiki/Geometric_progression – David Dec 13 '17 at 03:01