below is $a_n$
\begin{cases} 0 & n = 0 \\ 9 & n = 1 \\ 7a_{n-2} + 6a_{n-1} + 5^n & n > 1 \end{cases}
$S(n): \forall n \in \mathbb N, a_n \leq 3 \cdot7^n -d\cdot5^n$
Basis:
for $n = 0$
$a_n = 1 \leq 3 - d = 3 \cdot 7^0-d\cdot5^0 = 3 \cdot7^n -d\cdot5^n$ [def of $S(0)$], holds
Therefore we need $1 \leq 3 -d$
for $n=1$
$a_n = 9 \leq 27 - 5d = 3 \cdot 7^1-d\cdot5^1 = 3 \cdot7^n -d\cdot5^n$ [def of $S(1)$], holds
Therefore we need $9 \leq 27 - 5d$
Inductive step: let $n > 1$
Suppose $a_j \leq 3 \cdot 7^j - 5^j\cdot d$, whenever $0 \leq j < n$ [I.H]
WTP: $a_n \leq 3 \cdot 7^n - 5^n d$
$a_n = 7a_{n-2} + 6a_{n-1} + 5^n$ [def of $a_n$; $n > 1]$
$\leq 7(3 \cdot 7^{n-2} - 5^{n-2}d) + 6(3 \cdot 7^{n-1} - 5^{n-1}d) + 5^n$ [I.H]
$= 3\cdot7^{n-1} - 7 \cdot 5^{n-2}d + 18 \cdot 7^{n-1} - 6 \cdot 5^{n-1}d + 5^n$ [expanded]
$= 7^{n-1} (3 + 18) - 5^{n-2}(37d + 25)$ [common factor]
$= 7^{n-1}(21) - 5^{n-2}(37d + 25)$
I'm confused on how to achieve the WTP(what to prove) and find sufficient d. The original question was $S(n): \forall n \in \mathbb N, a_n \leq 3 \cdot7^n$ but the $5^n$ was impossible to work around