Question

Prove or disprove (from i=0 to n) sum([2i]^4) <= (4n)^4. If true use induction, else give the smallest value of n that it doesn't work for.

Answer 1

Answer:

The statement is true for every n between 0 and 77 and it is false for $n\geq 78$

Step-by-step explanation:

First, observe that, for n=0 and n=1 the statement is true:

For n=0: $\sum^{n}_{i=0} (2i)^4=0 \leq 0=(4n)^4$

For n=1: $\sum^{n}_{i=0} (2i)^4=16 \leq 256=(4n)^4$

From this point we will assume that $n\geq 2$

As we can see, $\sum^{n}_{i=0} (2i)^4=\sum^{n}_{i=0} 16i^4=16\sum^{n}_{i=0} i^4$ and $(4n)^4=256n^4$. Then,

$\sum^{n}_{i=0} (2i)^4 \leq(4n)^4 \iff \sum^{n}_{i=0} i^4 \leq 16n^4$

Now, we will use the formula for the sum of the first 4th powers:

$\sum^{n}_{i=0} i^4=\frac{n^5}{5} +\frac{n^4}{2} +\frac{n^3}{3}-\frac{n}{30}=\frac{6n^5+15n^4+10n^3-n}{30}$

Therefore:

$\sum^{n}_{i=0} i^4 \leq 16n^4 \iff \frac{6n^5+15n^4+10n^3-n}{30} \leq 16n^4 \\\\ \iff 6n^5+10n^3-n \leq 465n^4 \iff 465n^4-6n^5-10n^3+n\geq 0$

and, because $n \geq 0$,

$465n^4-6n^5-10n^3+n\geq 0 \iff n(465n^3-6n^4-10n^2+1)\geq 0 \\\iff 465n^3-6n^4-10n^2+1\geq 0 \iff 465n^3-6n^4-10n^2\geq -1\\\iff n^2(465n-6n^2-10)\geq -1$

Observe that, because $n \geq 2$ and is an integer,

$n^2(465n-6n^2-10)\geq -1 \iff 465n-6n^2-10 \geq 0 \iff n(465-6n) \geq 10\\\iff 465-6n \geq 0 \iff n \leq \frac{465}{6}=\frac{155}{2}=77.5$

In concusion, the statement is true if and only if n is a non negative integer such that $n\leq 77$

So, 78 is the smallest value of n that does not satisfy the inequality.

Note: If you compute  $(4n)^4- \sum^{n}_{i=0} (2i)^4$ for 77 and 78 you will obtain:

$(4n)^4- \sum^{n}_{i=0} (2i)^4=53810064$

$(4n)^4- \sum^{n}_{i=0} (2i)^4=-61754992$