Highschool induction (getting stuck on part 2)

Question

I'm getting stuck on part 2 of an induction question. I genuinely wish to only receive a helpful hint for it and would rather be able to crack the problem myself. All help is highly appreciated!

Here is the two parts of the question

i) Prove by induction that

$\ 1^{2} + 2^{2} + 3^{2} + ... + n^{2} = \frac{1}{6}n(n+1)(2n+1)\ $ (This is fairly easy and I had no problem getting this

ii) Hence find the least value of n for which $\frac{1}{6}n(n+1)(2n+1) \geq 10^{9}\ $

I have no idea how to approach it? I have tried to use part 1 but my attempt seemed to be in vain as I got to nowhere.

Answer 1

First let's expand your equation to get $2n^3 + 3n^2 + n \geq 6 \times 10^9$.

Now you had asked how to solve such a cubic. There is in fact a general cubic root equation, but it is quite the complicated beast so if you were attempting this on paper, perhaps with the aid of a basic calculator, here is another way to go about this specific question.

Note that the required constant, $6\times 10^9$ is large enough for our equation to enable us to more or less consider each power of $n$ separately. That is, we can refine our approach to looking first for the approximate $n$ for which $n^3 \geq 3 \times 10^9$ holds true. We know $n$ must be somewhere between $10^3$ and $2\times 10^3$ as those values give us $n^3 = 10^9$ and $n^3 = 8\times10^9$, so let us try $1.5 \times 10^3$ as it is half way between the two values. Either by hand or with a calculator it is not too difficult to show that $1.5^3 = 3.375$, which is really close to what we want so check $1.4$... $1.4^3 = 2.744$! Now $n$ is constrained between $1.4\times 10^3$ and $1.5\times 10^3$. Further refinements require actually considering the lower powers, in the process of calculating $1.4^3$ you have the values for the full cubic: for $n=1.4\times 10^3$ the cubic is $5\,488\,005\,600$ and we have only two digits to work with as the true $n$ is somewhere between $n=1400$ and $n=1500$. Do you see how to continue this process to find $n$?

Answer 2

Here's a suggestion: Take your inequality and divide it by $\:10^9\:$, distributing the divisor equally among the three factors on the left side. That would look like this:

$$ \begin{align} \color{white}{text}\\ \frac{1}{6}n(n+1)(2n+1) &\geq 10^{9}\\[2ex] \frac{1}{6} \left(\frac{n}{10^3}\right)\left(\frac{n+1}{10^3}\right)\left(\frac{2n+1}{10^3}\right) &\geq \frac{10^9}{10^9}\\[2ex] \frac{1}{6} \left(\frac{n}{1000}\right)\left(\frac{n}{1000}+\frac{1}{1000}\right)\left(\frac{2n}{1000}+\frac{1}{1000}\right) &\geq 1\\[2ex] \color{white}{text}\\ \end{align} $$

Now let $\: \alpha = \dfrac{n}{1000}\:$; then the inequality becomes

$$\color{white}{text}\\ \frac{1}{6} \left(\alpha\right)\left(\alpha+\frac{1}{1000}\right)\left(2\alpha+\frac{1}{1000}\right) \geq 1\\ \color{white}{text}\\$$

We can estimate that $\:n \gt 10^3\:$, so $\:\alpha \gt 1\:$; thus to estimate $\:n\:$, we can ignore the two $\:\dfrac{1}{1000}\:$'s in the last two factors (as they will not change the solution by a significant amount). The inequality then becomes

$$ \begin{align} \frac{1}{6} \left(2\alpha^3\right) &\geq 1\\ \alpha^3 &\geq 3\\[1ex] \alpha &\geq \sqrt[3]3 \approx 1.442\\[1ex] n &= 1000 \alpha \approx 1442\\ \color{white}{text}\\ \end{align} $$

Of course this may not be the exact value as we did "fudge" by eliminating the $\:\dfrac{1}{1000}\:$'s from the inequality; a little trial and error should reveal the correct value for $\:n\:$.

Answer 3

The cubic exceeds $\frac13n^3$, so $n_0:=\left\lceil\sqrt[3]{3\times 10^9}\right\rceil$ overestimates the least $n$ for which $f(n):=\frac16 n(n+1)(2n+1)\ge 10^9$. We can gradually reduce $n$ by subtracting squares, thereby using (i). The question clearly wants you to do that, or it wouldn't say "hence". You won't have to step back often, because the error term is $O(n^2)$. In fact $n_0=1443\implies f(n_0)=1002603134$, so my mental arithmetic says the correct answer is $1442$.

Answer 4

Hint: (as you wanted only a hint)

You may rewrite the formula as follows

$$\frac{1}{6}n(n+1)(2n+1) = \frac{1}{3}n\left(n+\frac{1}{2}\right)(n+1)$$

Now, you get a very useful estimate:

$$\frac{1}{3}n^3 \leq \frac{1}{3}n\left(n+\frac{1}{2}\right)(n+1) \leq \frac{1}{3}(n+1)^3$$