A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

Define \[f:\mathbb{N}\rightarrow \mathbb{N}\] by \[f(1)=2, f(2)=-8 \], for \[n\geq 3\] \[f(n)=8f(n-1)-15f(n-2)+6*2^n\] Prove that for all n\in \mathbb{N}, \[f(n)=-5*3^n+5^{n-1}+2^{n+3}\] Any help. I am stuck on the inductive step

  • This Question is Closed
  1. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \[f(n)=-5*3^{k+1}+5^{k}+2^{k+4}\] \[f(n)=8f(k)-15f(k-1)+6*2^{k+1}\] Then I dont know where to go from here.

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    suppose $$f(n-1)=-5\cdot3^{n-1}+5^{n-2}+2^{n+2}\\f(n)=-5\cdot3^n+5^{n-1}+2^{n+3}$$now we have $$\begin{align*}f(n+1)&=8 f(n)-15 f(n-1)+6\cdot 2^{n+1}\\&=8\left(-5\cdot3^n+5^{n-1}+2^{n+3}\right)-15\left(-5\cdot 3^{n-1}+5^{n-2}+2^{n+2}\right)+6\cdot 2^{n+1}\\&=-40\cdot 3^n+8\cdot 5^{n-1}+8\cdot 2^{n+3}+75\cdot 3^{n-1}-15\cdot 5^{n-2}-15\cdot2^{n+2}+6\cdot 2^{n+1}\\&=(-40+25)\cdot 3^n+(8-3)\cdot 5^{n-1}+(8\cdot 2-15+3)\cdot 2^{n+2}\\&=-15\cdot 3^n+5\cdot 5^{n-1}+4\cdot 2^{n+2}\\&=-5\cdot 3^{n+1}+5^n+2^{n+4}\end{align*}$$

  3. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    http://www.mathblog.dk/strong-induction/

  4. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Are you sure it's \(f(2)=8\)? @keynote

  5. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    he meant \(f(2)=-8\)

  6. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    it's obvious to solve $$f(n)=8f(n-1)-15f(n-2)+6\cdot 2^n$$ suppose \(f(n)=k\cdot 2^n\), so $$k\cdot 2^n=8k\cdot 2^{n-1}-15k\cdot 2^{n-2}+6\cdot 2^n\\4k\cdot 2^{n-2}-16k\cdot 2^{n-2}+15k\cdot 2^{n-2}-24\cdot 2^{n-2}=0\\2^{n-2}\left(4k-16k+15k-24\right)=0\\3k-24=0\\k-8=0\\k=8$$ so $$f(n)=8\cdot 2^n=2^{n+3}$$ is the particular solution to the recurrence

  7. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    and then we find the homogeneous solution with \(f(n)=r^n\) so $$r^n=8r^{n-1}-15r^{n-2}\\r^{n-2}(r^2-8r+15)=0\\(r-5)(r-3)=0\implies r\in \{3,5\}$$ so \(f(n)=A\cdot 3^n+B\cdot 5^n\) is the general solution to the homogeneous problem and \(f(n)=A\cdot 3^n+B\cdot 5^n+2^{n+3}\) where \(A,B\) are determined using initial conditions

  8. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so here we want \(f(1)=2,f(2)=-8\) giving $$f(1)=A\cdot 3+B\cdot 5+16\\f(2)=A\cdot 9+B\cdot 25+32$$ giving a system in \(A,B\): $$3A+5B+16=2\\9A+25B+32=-8\\\text{rewriting gives:}\\ 3A+5B=-14\\9A+25B=-40$$ we can cancel so: $$9A+15B=-42\\9A+25B=-40$$ subtracting the first from the second: $$10B=-40+42=2\\B=\frac15$$and similarly $$15A+25B=-70\\9A+25B=-40$$ giving $$6A=-30\\A=-5$$ which yields $$f(n)=-5\cdot 3^n+\frac15\cdot 5^n+2^{n+3}=-5\cdot 3^n+5^{n-1}+2^{n+3}$$

  9. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @oldrin.bataku I updated it. I had made a typo

  10. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    that is irrelevant, I already knew what you meant

  11. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Just to offer another method of solving, you can try finding the generating function \(F(x)=\sum\limits_{n=1}^\infty f(n)x^n\). Far less efficient, but it's a pretty useful technique nonetheless. \[\begin{align*}F(x)&=\sum_{n=1}^\infty f(n)x^n\\[1ex] &=\sum_{n=3}^\infty f(n)x^n+2x-8x^2\\[1ex] &=\sum_{n=3}^\infty \bigg(8f(n-1)-15f(n-2)+6\times2^n\bigg)x^n+2x-8x^2\\[1ex] &=8\sum_{n=3}^\infty f(n-1)x^n-15\sum_{n=3}^\infty f(n-2)x^n+6\sum_{n=3}^\infty(2x)^n+2x-8x^2\\[1ex] &=8x\sum_{n=3}^\infty f(n-1)x^{n-1}-15x^2\sum_{n=3}^\infty f(n-2)x^{n-2}+\frac{48x^2}{1-2x}+2x-8x^2\\[1ex] &=8x\sum_{n=2}^\infty f(n)x^n-15x^2\sum_{n=1}^\infty f(n)x^n+\frac{48x^2}{1-2x}+2x-8x^2\\[1ex] &=8x\left(\sum_{n=1}^\infty f(n)x^n-2x\right)-15x^2\sum_{n=1}^\infty f(n)x^n+\frac{48x^2}{1-2x}+2x-8x^2\\[1ex] &=8x(F(x)-2x)-15x^2F(x)+\frac{48x^2}{1-2x}+2x-8x^2\\[1ex] F(x)&=\frac{\dfrac{48x^2}{1-2x}+2x-24x^2}{1-8x+15x^2} \end{align*}\]where \(f(n)\) is the coefficient of the \(n\)th term of the Taylor expansion of \(F\) around \(x=0\). Finding a closed form for the coefficient is tedious, but it can be done. W|A agrees: http://www.wolframalpha.com/input/?i=McLaurin+series+of+%2848x%5E3%2F%281-2x%29%2B2x-24x%5E2%29%2F%281-8x%2B15x%5E2%29

  12. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah, that's also called the Z transform

  13. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.