## 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

1. anonymous

$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

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
4. anonymous

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

5. anonymous

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

6. anonymous

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

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 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

10. anonymous

that is irrelevant, I already knew what you meant

11. anonymous

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

yeah, that's also called the Z transform