Hi, I've been trying to demonstrate this:

I know that $d_1=1, d_2=10, d_3=50, d_4=248$ and for $n \geq 5 ,d_n = 5d_{n-1} - 4d_{n-4} $. Demonstrate for all

$n \in \mathbb{N} $ that: $$P(n): d_n < n \cdot 3^{n+1}. $$

I need to demostre this using the induction principle. My doubt is in the second part of the demonstration.

First, I check if P(1) until p(4) is true

$d_1=1 \geq 3$ so P(1) verifies

$d_2=10 \geq 2\cdot3^{3}=18$ so P(2) verifies.

$d_3 = 50 < 3 \cdot 3^{3+1} = 243$ so P(3) verifies.

$d_4 = 248 < 4 \cdot 3^{4+1} = 972$ so P(4) verifies.

Now, the second part is where I have the problem. I do not know what to do. I understand the theory but I don't know how to apply it. This is what I thought

Then, I assume true P(n) for $n \in \mathbb{N}$ and $n \geq 5$ is true, so

$$d_n < n \cdot 3^{n+1}. \text{ is true}$$

We know too that for $n \geq 5, d_n = 5d_{n-1} - 4d_{n-4}$, so

$d_{n+1} = 5d_{n} - 4d_{n-3}$. Later, we clear $$5d_{n}=d_{n+1}+4d_{n-3}.$$

Then, by Inductive Hypothesis I deduce that:

$$5d_n < 5n \cdot 3^{n+1}.$$

So:

$$ d_{n+1}+4d_{n-3}< 5n \cdot 3^{n+1}$$

Then

$$d_{n+1}<d_{n+1}+4d_{n-3}< 5n \cdot 3^{n+1}.$$

I want to demonstrate that $d_{n+1}<(n+1)3^{n+2}.$

So i tried to compare $5n \cdot 3^{n+1}$ and $(n+1)3^{n+2}$ trying to prove that

$$5n \cdot 3^{n+1}<(n+1)3^{n+2}.$$

If someone find a way or give me some advice, pls write it.

My English is not good at all, but I tried my best.

Thanks in advance,

Raimaths