Prove summation using induction

$$\sum\limits_{i=1}^n i^3 = \left(\frac{n(n + 1)}{2}\right)^2$$

My basis step is $P(1)$ sets the $LHS = RHS = 1$.

For the inductive step, I assume $n = k$ holds for $k+1$. On the $RHS$:

$$\left(\frac{(k + 1)((k + 1) + 1)}{2}\right)^2$$

But I don't know how to convert the summation into something that can evaluated algebraically.

Disclaimer: this is a question from an exam review sheet.

Answer

I assume that $P(n)$ means that the formula holds for $n$.

You assume that this holds for $n=k$ and you want to show that this holds for $n = k+1$.
On the right hand side you indeed have what you have written.

One the left hand side you have
$$
\sum_{i=1}^{k+1} i^3 = \left[\sum_{i=1}^{k} i^3\right] + (k+1)^3
$$
Now you can use the induction hypothesis and continue to get

$$
\left[\sum_{i=1}^{k} i^3\right] + (k+1)^3 = \left(\frac{k(n+1)}{2}\right)^2 + (k+1)^3.
$$
All that is left for you to show is that
$$
\left(\frac{k(n+1)}{2}\right)^2 + (k+1)^3
$$
is equal to the right hand side that you have in your question.

asymptotics - Big Oh notation/estimation

I have recently encountered a series of perturbation problems in which the Big Oh notation is used frequently. Since I have not encountered this notation before, I am a little bit confused about it. I have read various websites about it, and I get the idea behind it (I also can quite easily look at a function and determine what order the function has), but a few statements in my text book still leave me confused.

For instance, in my book it says the following at one point:

Consider

$q(x,\epsilon) = y_{0} + y_{1} = e^{1-x} + e(1 - e^{-x/ \epsilon})$

If $x = O(1)$, then

$q(x, \epsilon) = e^{1-x} + e + O(\epsilon)$

I am a little bit confused about the whole "If $x = O(1)$, then. . ." part of the problem. Why is it here necessary to state this? Is this because, if $x = O(1)$, then we have $x < A$, where $A$ is a constant? Thus $x$ does not approach infinity, and then the last estimation above follows? Is this correct reasoning? This is what I assume based on how I've interprerted the definition of Big Oh, but I could be wrong here.

I would greatly appreciate it if someone could explain this to me.

Answer

I think there is confusion because usually when we talk about Big-Oh, it is assumed that $n\rightarrow\infty$. However, when we are talking about 'small quantities' like $\epsilon$, then we mean that $\epsilon\rightarrow0$ instead. You can think of it as $\epsilon=\frac{1}{n}\rightarrow 0$.

You can see the term $e^{1-x/\epsilon}$ is smaller than $\epsilon$. So we say it is $O(\epsilon)$. A graph on wolframalpha may convince you by ploting $e^{1-1/x}-x$ on x=0..1. See here

applications - Unit decomposition by three continuous functions

My current research project involves adaptive weights for three different loss functions so that I hope each the objective can focus on the different size of objects when given a different size of the input.

Say there are three ranges: $0-300$ is for small objects, $300-900$ is for middle-sized objects and $>900$ is for large objects.

My current design: let's assume input is $x$,
$$

\begin{align*}
y_1&=\frac{1}{1+\exp(-0.01(x-600))}\\
y_2&=\frac{1}{1+\exp(+0.01(x-600))}\\
y_3&= \frac{1}{1 + \exp(-0.02*(x-300)))}+ \frac{1}{1 + \exp(0.02*(x-900))}-1
\end{align*}
$$

It gives that

However, the problem is $\sum_{i=1,2,3} y_i[x]\neq 1, \forall 0\leq x$. A simple solution to fix is to design two piece-wise functions:
$$
\begin{align*}
y_1&=\frac{1}{1 + \exp(-0.02(x-300)))}+ \frac{1}{1 + \exp(0.02(x-900))}-1\\
y_2&=\frac{1}{1- \exp(+0.02(x-300))}+ \frac{1}{1 + \exp(-0.02(x-900))},
\end{align*}
$$
where $x<600$ for high-pass filter in $y_1$ and $x>600$ for low-pass filter in $y_1$ is zero.

However, I prefer the first continuous functions for its simplicity. By any chance, there exists a more elegant solution where three functions are unit decomposition and not piece-wise? Thanks ahead for any suggestions.

real analysis - Proof that limit as n approaches inf of $3^n cdot frac{1}{n!} = 0$ using squeeze theorem

This is a homework question. I'm completely new to epsilon proofs, so I'm pretty bad at them.

I want to prove that $3^n \cdot \frac{1}{(n!)} = 0$ converges to 0.

Here's where I'm at. By the definition of a limit of a sequence, I want

$\forall \epsilon>0 \exists N \in \mathbb{N} $ such that $\mid \frac{3^n}{n!} - 0 \mid < \epsilon$.

Or, I want to use the squeeze theorem to bound it below and above with functions with limits of 0.

I started to try to get an appropriate value for N, but it doesn't seem to work out... I'm using the arbitrarily small $\epsilon$ to try to find an N for which $\frac{3^n}{n!} < \epsilon$ for all n > N. I've just tried doing algebraic manipulation, but I haven't got anywhere.

For the squeeze theorem, I thought of trying to bound the sequence between the sequences $x_n = \frac{1}{n}$ and $z_n = 0$. But I would have to prove that $\frac{3^n}{n!}$ is bounded above by $\frac{1}{n}$, which I'm not sure I know how to do.

If you could tell me which of the two methods would be appropriate and some hints for how to proceed I would appreciate it, thanks.

calculus - Limit Proof Question

How to prove $\lim_{n\to\infty}\frac{f(x)}{g(x)} = \frac{\lim_{n\to\infty} f(x)}{\lim_{n\to\infty}g(x)}=\frac{L}{M}$ if g(x) is not equal to 0 using $\epsilon-\delta$ definition. I know the proof that uses the idea of $\frac{1}{g(x)}$ and the uses multiplication rule of limit, but I am wondering if there is a direct and more elegant proof.

How to solve this set of symmetric polynomial expressions

So there's this set of polynomial expressions with degree n=3:

$$
\left\{
\begin{array}{c}
x_1 + x_2 + x_3 = a \\
x_1^2 + x_2^2 + x_3^2 = b \\
x_1^3 + x_2^3 + x_3^3 = c
\end{array}
\right.
$$

How to find atleast one set of x1,x2,x3 values, knowing that all variables and constants (a,b,c) are positive integers?

Thank you.

---

Update:

Alright, with the help in the comments I was able to transform this set into a single polynomial expression that can be solved in various ways.

Using Newton's identities:
$$
\begin{array}{}
x_1^2 + x_2^2 + x_3^2 = (x_1 + x_2 + x_3)^2 - 2(x_1x_2 + x_2x_3 + x_1x_3) \\
x_1^3 + x_2^3 + x_3^3 = (x_1 + x_2 + x_3)^3 - 3(x_1x_2 + x_2x_3 + x_1x_3)(x_1 + x_2 + x_3) + 3x_1x_2x_3
\end{array}
$$

We can substitute expressions in the set:

$$
\left\{
\begin{array}{}
x_1 + x_2 + x_3 = a \\
(x_1 + x_2 + x_3)^2 - 2(x_1x_2 + x_2x_3 + x_1x_3) = b \\
(x_1 + x_2 + x_3)^3 - 3(x_1x_2 + x_2x_3 + x_1x_3)(x_1 + x_2 + x_3) + 3x_1x_2x_3 = c
\end{array}
\right.
$$

$$
\left\{
\begin{array}{}
x_1 + x_2 + x_3 = a \\
x_1x_2 + x_2x_3 + x_1x_3 = \frac{a^2 - b}{2} \\
(x_1 + x_2 + x_3)^3 - 3(x_1x_2 + x_2x_3 + x_1x_3)(x_1 + x_2 + x_3) + 3x_1x_2x_3 = c
\end{array}
\right.
$$

$$
\left\{
\begin{array}{}
x_1 + x_2 + x_3 = a \\
x_1x_2 + x_2x_3 + x_1x_3 = \frac{a^2 - b}{2} \\
x_1x_2x_3 = \frac{c + 3a\frac{a^2-b}{2} - a^3}{3}
\end{array}
\right.
$$

To simplify, let's assume (since the right halves of the last set are all constants):

$$
\begin{array}{}
p_1 = a \\
p_2 = \frac{a^2 - b}{2} \\
p_3 = \frac{c + 3a\frac{a^2-b}{2} - a^3}{3}
\end{array}
$$

So we get:

$$
\left\{
\begin{array}{}
x_1 + x_2 + x_3 = p_1 \\
x_1x_2 + x_2x_3 + x_1x_3 = p_2 \\
x_1x_2x_3 = p_3
\end{array}
\right.

$$

Now, using Viete's theorem for general polynomial of degree 3:

$$
P(x) = a_3t^3 + a_2t^2 + a_1t + a_0
$$

With the following properties:

$$
\begin{array}{}
t_1 + t_2 + t_3 = -\frac{a_2}{a_3} \\
t_1t_2 + t_2t_3 + t_1t_3 = \frac{a_1}{a_3} \\
t_1t_2t_3 = -\frac{a_0}{a_3}
\end{array}
$$

Applying to our set:

$$
\left\{
\begin{array}{}
p_1 = -\frac{a_2}{a_3} \\
p_2 = \frac{a_1}{a_3} \\
p_3 = -\frac{a_0}{a_3}
\end{array}
\right.
$$

And assuming that $a_3 = 1$, the final polynomial will be the following:

$$
t^3 - p_1t^2 + p_2t - p_3 = 0,
$$

where the three roots of $t$ are variables $x_1, x_2$ and $x_3$.

(Using Buchberger's algorithm might be a good way to solve it a well, but I was struggling with it and decided to do it this way for now.)

Answer

Take the resultant of $x_1 + x_2 + x_3 - a$ and $x_1^2 + x_2^2 + x_3^2 - b$ with respect to $x_3$, the resultant of $x_1 + x_2 + x_3 - a$ and $x_1^3 + x_2^3 + x_3^3 - c$ with respect to $x_3$, and the resultant of those two resultants with respect to $x_2$. You get the square of a cubic polynomial in $x_1$ that must be $0$:

$$ -6\,{x_{{1}}}^{3}+6\,a{x_{{1}}}^{2}+ \left( -3\,{a}^{2}+3\,b \right) x
_{{1}}+{a}^{3}-3\,ab+2\,c
$$

Since it's a cubic with real coefficients, there is at least one real root.
The discriminant is $$\Delta = -216\,{a}^{6}+1944\,{a}^{4}b-1728\,{a}^{3}c-4536\,{a}^{2}{b}^{2}+7776
\,abc+648\,{b}^{3}-3888\,{c}^{2}
$$

If $\Delta > 0$, there are three distinct real roots; if $\Delta < 0$, there is only one real root. If $\Delta = 0$, there is at least one real root of multiplicity $> 1$. However, even when there is a real root for $x_1$ the solutions for $x_2$ and $x_3$ might not be real. By symmetry, in any solution the values of $x_2$ and $x_3$ are also possible values of $x_1$. Thus if we want real solutions for $x_1, x_2, x_3$ we need $\Delta \ge 0$.

algebra precalculus - Proving an inequality $log$ and $e$

This inequality should be fairly easy to show. I think I'm just having trouble looking at it the right way (It's used in a proof without explanation).

$$(1-\frac{1}{\log ^{2} n})^{(2 \log n) -1}\geq e^{-2/\log n}$$

Any help is much appreciated. Thanks
Edit: Log is base 2

Answer

Assuming $n>2$ are natural numbers and $\log = \log_2$:

$(1 + \frac 1n)^n$ is increasing, $\lim_{n\to \infty}(1+ \frac 1n)^n =e $ and $(1+\frac 1x)^x < e$ for $x \ge 1$.

And $(1-\frac 1x)^x > \frac 1e$ for $x \ge 1$.

So $ (1 - \frac 1{\log^2 n})^{\log^2 n} > e^{-1}$

$( 1 - \frac 1{\log^2 n})^{2\log n} > e^{\frac{-2}{\log n}}$

$( 1 - \frac 1{\log^2 n})^{2\log n - 1} > \frac {e^{\frac{-2}{\log n}}}{1 - \frac 1{\log^2 n}}$

If $n > 2$ and $\log n = \log_2 n > 1$ then $0< {1 - \frac 1{\log^2 n}} < 1$ and

$( 1 - \frac 1{\log^2 n})^{2\log n - 1} > \frac {e^{\frac{-2}{\log n}}}{1 - \frac 1{\log^2 n}}>e^{\frac{-2}{\log n}} $

If $n = 2$ then

$( 1 - \frac 1{\log^2 n})^{2\log n - 1} =$

$( 1 - \frac 1{\log^2 2})^{2\log 2 - 1} = 0^0$ is undefined.

Likewise if $n=1$ we have division by $0$.

Perhaps $\log = \ln =\log_e$?