1. Demonstration by Induction

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.

Raimaths

2. Re: Demonstration by Induction

$\displaystyle d_9 = 752596$

is not less than

$\displaystyle 9 * 3^{10}=531441$

3. Re: Demonstration by Induction

It's true. Sorry, I have made an error copying it. I'll change it.

4. Demonstration by Induction Correct

Im my last post I made and error copying the wording. So, I changed and tried to solve it again, but here I am again. My doubt is again in the second part of the demonstration. The wording is the same, but changing < for >.

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 N$ and $n \geq 9$ that:
$$P(n):d_n > n \cdot 3^{n+1}.$$

As you could see at the last message, changing "<" for ">", We notice that for $d_1$ to $d_8$ the proposition for these $n$ values is false ($P(1...8)$ is false). However, like Idea said, applying it to his new wording, $P(9)$ is true. Ive verified it for $n=10,n=11$ and $n=12$ too. So its seem that for $n \geq 9$ ($n \in N$) $P(n)$ is true.

Applying demonstration by induction:

(1) We see that $d_9= 752596 > 9 \cdot 3^{10}=531441$, so $P(9)$ is true.
(2) Then, I assume true $P(n)$ for $n \in N$ and $n \geq 9$ is true, so
$$d_n>n\cdot3^{n+1}.$$

I want to demonstrate $d_{n+1}>(n+1)\cdot3^{n+2}.$

I know that $d_{n+1}=5d_n - 4d_{n-3}$ so byInductive Hypothesis $d_{n+1}=5d_n - 4d_{n-3}>5n3^{n+1} -4d_{n-3}$. One thing I tried, is comparing $5n \cdot 3^{n+1} - 4d_{n-3}$ and $(n+1)\cdot3^{n+2}$.

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

5. Re: Demonstration by Induction

Let
$\displaystyle c_n=d_n-d_{n-1}$

1) Show that $\displaystyle c_n=4\left(c_{n-1}+c_{n-2}+c_{n-3}\right)$

2) Use (1) and induction to prove $\displaystyle c_n>3^n(2n+1)$

3) use induction again to show

$\displaystyle d_n=d_{n-1}+c_n>(n-1)3^n+(2n+1)3^n=n 3^{n+1}$