TITLE: for all $n \in \mathbb N f(n) \leq 7 \cdot 5^n - 3^n$, also $f(n) \leq c \cdot 5^n$
QUESTION [0 upvotes]: Base Case:
Let n = 0
$f(n) = 6$ [def of f]
$\leq 7 - 1 = 6 = 7 \cdot 5^0 - 3^0 = 7 \cdot 5^n - 3^n$
as wanted
IND STEP: Let $n > 0$. Suppose $f(n) \leq 7 \cdot 5^n - 3^n$ [IH]
Trying to show: $f(n+1) \leq 7 \cdot 5^{n+1} - 3^{n+1}$
$f(n+1) = 5f(n) + 3^n$ [Definition of f; $n > 0$]
$ \leq 5 \cdot 7 \cdot 5^n - 5\cdot 3^n + 3^n$ [IH]
$ = 7 \cdot 5^{n+1} - 3^n (5-1)$ [Algebra]
$= 7 \cdot 5^{n+1} - 3^{n}(4)$
$\leq 7 \cdot 5^{n+1} - 3^{n}(3)$
$= 7 \cdot 5^{n+1} - 3^{n+1}$
as wanted
How do I find c?

REPLY [0 votes]: $$f(n) \leq 7(5^n)-3^n \leq 7(5^n)$$
Hence you can pick $c=7$.
{"set_name": "stack_exchange", "score": 0, "question_id": 2479642}