Question

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

Answer 1

\[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.

Answer 2

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*}$$

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

That would definitely make more sense.

Solution with \(f(2)=\color{red}+8\):
http://www.wolframalpha.com/input/?i=RSolve%5B%7Bf%5Bn%5D%3D%3D8f%5Bn-1%5D-15f%5Bn-2%5D%2B6+2%5En%2Cf%5B1%5D%3D%3D2%2Cf%5B2%5D%3D%3D8%7D%2Cf%5Bn%5D%2Cn%5D

Solution with \(f(2)=\color{red}-8\):
http://www.wolframalpha.com/input/?i=RSolve%5B%7Bf%5Bn%5D%3D%3D8f%5Bn-1%5D-15f%5Bn-2%5D%2B6+2%5En%2Cf%5B1%5D%3D%3D2%2Cf%5B2%5D%3D%3D-8%7D%2Cf%5Bn%5D%2Cn%5D

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

that is irrelevant, I already knew what you meant

Answer 12

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

Answer 13

yeah, that's also called the Z transform