Consider the following recurrence defining a function $f : \mathbb N \to \mathbb N$.
$$ f(n) = \begin{cases} 5 & n = 0 \\ 4f(n-1) + 3 \cdot 2^{n-1} & n > 0 \end{cases} $$
Use induction to find positive constants $c, d \in \mathbb R$ such that $f(n) = c4^n - d2^n$ for all $n \in \mathbb N$
ANSWER:
Basis: let $n = 0$
$f(0) = 5$ [By definition of F]
therefore, inorder for this to hold we need
$$5 = c4^5 - d2^5 \text{ } [*]$$
Ind step: let $n > 0$. Suppose $f(j) = c4^j - d2^j$ whenever $0 \leq j < n$ [I.H]
WTP: $f(n) = c4^n - d2^n$
$f(n) = 4f(n-1) + 3 \cdot 2^{n-1}$ [Definition of f; $n > 0$]
$= 4(c4^{n-1} - d2^{n-1}) + 3 \cdot 2^{n-1}$ [I.H]
$= c4^{n} - 4d2^{n-1} + 3 \cdot 2^{n-1}$ [Algebra]
Again, we need $f(n) \leq c4^n - d2^n $ so
$$c4^{n} - 4d2^{n-1} + 3 \cdot 2^{n-1} \leq c4^n - d2^n$$
$$3 \cdot 2^{n-1} \leq d(-2^n + 2^{n+1})$$
$$3 \cdot 2^{n-1} \leq d 2^n$$
$$\frac{3}{2} \leq d$$
so let $d = 3/2$ which would make $c = 53/1024$
Would this be correct?