No idea where to go with this,
Got a piecewise function $$ f(n) = \begin{cases} 1 & \text{when } n = 1 \\ 3 & \text{when } n = 2 \\ 5 & \text{when } n = 3 \\ 3\cdot f(n-1) + 2\cdot f(n-3) & \text{when } n \geq 4 . \end{cases} $$
and I have to show that the function has the property that $2^{n−1} \leq f(n) \leq 2^n$ for any $n$; lastly translate into big-O notation. But I have no idea how to go about this.
I figure I have the base case $f(1) = 1$, which it does as denoted by the first line 1, $n = 1$.
Then the assumption/induction, I just have $3\cdot f(k+1-2)+2\cdot f(k+1-3)$ and therefore have $3 \cdot f(k-1) + 2\cdot f(k-2)$ as my induction.
Proof under the correction that $f(n)=3f(n-2)+2f(n-3)$:
Base cases:
$2^0\le f(1)\le 2^1$
$2^1\le f(2)\le 2^2$
$2^2\le f(3)\le 2^3$
Induction step: For $n>3$, assume $2^{i-1}<f(i)<2^i$ for all $i<n$. In particular:
$2^{n-3}\le f(n-2)\le 2^{n-2}$ and
$2^{n-4}\le f(n-3)\le 2^{n-3}$
Multiply the first inequality with 3 and the second with 2
$3\cdot 2^{n-3}\le 3f(n-2)\le 3\cdot 2^{n-2}$ and
$2\cdot 2^{n-4}\le 2f(n-3)\le 2\cdot 2^{n-3}$
Adding the two inequalities gives:
$3\cdot 2^{n-3}+2\cdot 2^{n-4}\le 3f(n-2)+2f(n-3)\le 3\cdot 2^{n-2}+ 2\cdot 2^{n-3}$
But
$3\cdot 2^{n-3}+2\cdot 2^{n-4}=3\cdot 2^{n-3}+2^{n-3}=4\cdot 2^{n-3}=2^{n-1}$
$3f(n-2)+2f(n-3)=f(n)$ and
$3\cdot 2^{n-2}+2\cdot 2^{n-3}=3\cdot 2^{n-2}+2^{n-2}=4\cdot 2^{n-2}=2^{n}$
It follows that:
$2^{n-1}\le f(n)\le 2^n$ which was to be proved.