Recurrences - proof of induction

Question

So I have a question below that asks for a closed formula and for me to prove the formula using induction.

I believe I got the formula correct, but I'm having a hard time proving it because of the extra n.

1) Consider the function f:N→N defined by the recurrence:

$ f(n)= \begin{cases} \frac{1}{2}&\text{if}\, n= 1\\ \frac{1}{2}*n*f(n-1)&\text{if}\, n\geq 1\\ \end{cases} $

Write a closed form formula for f(n) and prove that your formula is correct.

My attempt:

So plugging in the values, I got 1/4, 2/8, 2/16, etc. This gave me a formula of n!/(2^(n+1)).

When I try to prove it using induction:

f(n) = (1/2) * n * f(n-1)

f(n) = (1/2) * n * n!/(2^(n+1-1))

Like I added the -1 on the denominator but I'm not sure if It should be added to the numerator as well? I'm not exactly sure what to do with the n on the 2nd term either.

I know the entire thing should eventually be reduced to n!/(2^(n+1)) but I'm getting stuck when I attempt to get there. I don't think I'm substituting everything correctly.

Answer 1

If suspected your closed expression is $$f(n)=\frac{n!}{2^{n+1}},$$ then $$f(42)=\frac{42!}{2^ {42+1}}$$ and $$f(17a+3b^5) = \frac{(17a+3b^5)!}{2^{17a+3b^5+1}}$$ and so on ...

And of course then $$ f(n-1)=\frac{(n-1)!}{2^{(n-1)+1}}=\frac{(n-1)!}{2^n}$$ is what you have to plug in for $f(n-1)$ in the course of the proof.

Answer 2

You find $f(n)=\frac{n!}{2^{n+1}}$. Let's check it: so, $f(n-1)=\frac{(n-1)!}{2^{n}}$ and we have $$\frac{n!}{2^{n+1}}=f(n)=\frac{1}{2}nf(n-1)\\=\frac{1}{2}n\frac{(n-1)!}{2^{n}}\\ =\frac{1}{2}\frac{n(n-1)!}{2^{n}}=\\ \frac{n(n-1)!}{2^{n}\cdot 2}=\\ \frac{n!}{2^{n+1}}$$

Answer 3

Actually, you have$$(\forall n\in\mathbb N):f(n)=\frac{n!}{2^n}.$$This is clearly true if $n=1$. And if $f(n-1)=\frac{(n-1)!}{2^{n-1}}$, then\begin{align}f(n)&=\frac12nf(n-1)\\&=\frac n2\times\frac{(n-1)!}{2^{n-1}}\\&=\frac{n!}{2^n}.\end{align}