So I have a question below that asks to find a closed-form formula for the following set and then prove it using induction. I'm pretty sure my formula is correct but I'm struggling to prove it.
1) Consider the function $f:\Bbb N^+→\Bbb N$ defined by:
$$ f(n)= \begin{cases} 1&\text{if}\, n∈ {1,2,3}\\ 4f(n-3)&\text{if}\, n> 3\\ \end{cases} $$
Write a closed form formula for $f(n)$ and prove that your formula is correct.
So I did:
$$f(1) = 1$$
$$f(2) = 1$$
$$f(3) = 1$$
$$f(4) = 4 * f(1) = 4 * 1 = 4$$
$$f(5) = 4 * f(2) = 4 * 1 = 4$$
$$f(6) = 4 * f(3) = 4 * 1 = 4$$
$$f(7) = 4 * f(4) = 4 * 4 = 16$$
$$f(7) = 4 * f(5) = 4 * 4 = 16$$
$$f(8) = 4 * f(6) = 4 * 4 = 16$$
and so on.
I believe the formula would be represented with the floor function as $4\left[\frac{(n - 1)}{3}\right]$. The issue is when I try to do my base case and proof of induction, my values don't seem to match.
Base case: $n = 1$
$$f(1) = 4\left[\frac{(1 - 1)}{3}\right].$$
$f(1) = 0$ which isn't right because it was stated that $f(1) = 1$ above.
When I try to prove it:
$$f(n-1) = 4f(n-3)$$
$$f(n-1) = 4*\left(4\left\lfloor\frac{(n - 1)}{3}\right\rfloor\right)$$
$$f(n-1) = 4*\left(4\left(\left\lfloor\frac{(n - 1 - 1)}{3}\right\rfloor\right)\right)$$
$$f(n-1) = 4*\left(4\left(\left\lfloor\frac{(n - 2)}{3}\right\rfloor\right)\right)$$
Which causes me to be stuck. I can't seem to properly evaluate the function to $4\left[\frac{(n - 1)}{3}\right]$.
Hint: Since you multiply by $4$ every thrid value, your variable $n$ should be in the exponent. $$f(n)=4^{\left\lfloor\frac{n-1}{3}\right\rfloor}$$