Let S = X1  * Y1 + X2 * Y2 + · · · + Xn * Yn,  where X1, X2 , . . . ,   Xn and Y1, Y2, . . . , Yn are orderings of two different sequences of   positive real numbers, each containing n elements.      a) Show that Stakes its maximum value overall orderings of the two   sequences when both sequences are sorted (so that the elements in each   sequence are in nondecreasing order).   I am new to mathematical proof and I really suffer from it, can anyone please help me with this problem?
121034
I am trying to improve my discrete Math skills by doing some proof exercises. But I am struggling to understand how to start proving the following hypothesis:  $$ S = {x}_1{y}_1 + {x}_2{y}_2 + \ldots + {x}_n{y}_n $$ Where ${x}_1,{x}_2\ldots{x}_n$ and ${y}_1,{y}_2\ldots{y}_n $ are ordering of two different sequences of positive real numbers, each containing n elements. S takes its maximum value when ${x}_1,{x}_2\ldots{x}_n$ and ${y}_1,{y}_2\ldots{y}_n $ are sorted in non decreasing order.  I was thinking that I should maybe use a proof by contradiction. Where the negation of the hypothesis is: S takes it minimum value over all ordering of the two sequences when both sequences are sorted into non increasing order.  However I am not sure my negation of the hypothesis is correct or how proceed from there. I do not want the complete proof because I am trying to learn how to do it myself but if some one can tell me how to make a start on this I would be grateful.
15071
Suppose $m, n$ are infinite ordinal numbers. $$a) m=n → |m|=|n|$$ $$b)|m|=|n| →m=n$$ $$c)m&lt;n→ |m|&lt;|n|$$ $$d)|\max{(m,n)}|&lt; |m|+|n|$$ $$e)|m|&lt;|n| →|m|^{|n|}&lt;|n|^m$$  Which of the above statements are true? (a) looks true but I do not know the way to work it out. Please help
120686
Consider the sequence defined by $a_1 = \sqrt{2}$, $a_2 = \sqrt{2 + \sqrt{2}}$, so that in general, $a_n = \sqrt{2 + a_{n - 1}}$ for $n &gt; 1$. I know 2 is an upper bound of this sequence (I proved this by induction). Is there a way to show that this sequence converges to 2? What I think is that the key step is to prove 2 is the least upper bound of this sequence. But how?
77867
Let $a$ and $b$ be positive numbers, and $n \in \mathbb{N}$. Prove that (using Rearrangement Inequality) $$(n+1)\left(a^{n+1}+b^{n+1}\right) \geq (a+b)\left(a^n+a^{n-1}b+\ldots+b^{n}\right). $$  Thanks :)
46211
Let $R$ be a total order on set $S$. Prove that if $S$ has a minimal element, than the minimum element is unique.  I have difficulties with proofs. I know any graph of a total order is a straight line, which clearly has a minimal element. How doI tell when something is mathematically proven?  EDIT: this is how I would prove it  Let $x, y \in S$ such that x and y are minimal. Since S is a total order $x$ and $y$ are comparable and either    case 1: one comes after the other and therefore one isn't the minimal case 2: both are the same and $x=y$  I know this isn't a mathy argument and could use help making it more presentable.
93883
A set $X$ together with a binary relation $\leq$ such that for all $x,y,z\in X$,  $O1$. $x\leq x$  $O2$. $x\leq y$ and $y\leq x$ then $x=y$  $O3$. $x\leq y$ and $y\leq z$ then $x\leq z$  is called an ordered or sometimes a partially ordered.  An ordered $(X,\leq)$ is called a total order if for all $x,y\in X$, either $x\leq y$ or $y\leq x$.  Question: Show that total orders are maximal orders  My question: is there a typo in the question?  What is a maximal order? How can I prove the question, can you help? Thanks...
16844
Suppose that we are trying to prove that for every positive integer n, if x and y are positive integers with max(x, y) = n, then x = y. For the base case, we suppose n = 1. If max(x, y) = 1 and x and y are positive integers, we have x = y = 1. Now we let k be a positive integer, and assume that whenever max(x, y) = k and x and y are positive integers, then x = y. Let max(x, y) = k + 1, where x and y are positive integers. Then max(x - 1, y - 1) = k, so by the inductive hypothesis, x - 1 = y - 1, so x = y. What is wrong with this ``proof''?
71840
Let $a$ be an element of maximum order from a finite Abelian group $G$. Prove that for any element $b$, $|b|$ divides $|a|$ (order of $b$ divides order of $a$).
111539
Is there a strictky increasing sequence $\{ a_k\}$  of positive integers such that $\sum 1/{a_k}$ is finite and minimal with respect to this property, in a sense that if $\{ b_k \}$ is another sequence of such, then $a_k \leq b_k$ for all but finitely many values of $k$?  Motivation came from comparing the series $\sum 1/n$ and $\sum 1/{n^2}$, the first of which is divergent but the second of which is not; the sequence for the first is "smaller" than that of the second.  If this question need be motified to make my question clearer, please comment/suggest adit as well.
14809
Let $n$ and $1\leq k \leq n$ be natural numbers. Prove the inequality     $$\sum_{i=k}^n \binom{n}{i}\bigg(\frac{k}{n+1}\bigg)^i\bigg(1-\frac{k}{n+1}\bigg)^{n-i} \leq 1 - \frac{1}{e} $$  Equivalently, if $X\sim$ Bin($n$,$\frac{k}{n+1}$), prove that $\mathbb{P}[X\geq k] \leq 1 - \frac{1}{e}$.   My attempt: It may be helpful to show that the LHS tends to $1-\frac{1}{e}$ as $n \to \infty$ (already did that) and that the LHS is an increasing function on $n$ (have not done that).
57722
Not sure how to approach this problem below. I tried assuming the conditional but that doesn't seem to get me anywhere.     If for a sequence of non-negative real numbers $\{a_n\}$, we have $$\sum{a_kb_k}$$ converges whenever $$\sum{b_k^2}$$ converges. then show that $$\sum{a_k^2}$$ converges
81903
Let $X_n$, $n=1,2,3,...$ be a sequence of independent (not necessarily identically distributed) random variables, let $S_n=\sum_{i=1}^nX_i$. Prove the following maximal inequality: For all $t&gt;0$,$$\mathbb{P}\left(\max_{1\leq i\leq n}|S_i|\geq t \right)\leq 3\max_{1\leq i\leq n}\mathbb{P}\left(|S_i|\geq\frac{t}{3} \right)$$
65826
My friend and I are currently debating the following question:      Let $y_n$ be a sequence in a metric space and assume that the subsequences    $y_{2n}$, $y_{2n + 1}$, and $y_{3n}$ all converge. What can we say about the sequence $y_n$?    To me it seems that all the subsequences will converge to a limit say $y$. Then any term in the original sequence will be in one of these subsequences, it follows that the entire sequence $y_n$ converges to $y$.  I let $\varepsilon &gt; 0$. Since $y_{2n}$ converges to $y$ there exists an index $2N$ such that $d(y_{2n},y) &lt; \varepsilon$ for $2n \geq 2N$, and since $(y_{2n+1})$ converges to $y$ there exists $2M + 1$ such that $d(y_{2n+1}, y) &lt; \varepsilon$ for $2n + 1 \geq 2M + 1$.  Let $m \geq \max\{2N,2M+1\}$. If  $m$ is even, since $m\geq 2N$ we have $d(y_m,y)&lt;\varepsilon$; if $m$ is odd, since $m\geq 2M+1$ we have $d(y_m,y)&lt;\varepsilon$. Thus $d(y_m,y)&lt;\varepsilon$ for any $m \geq \max\{2N,2M+1\}$, and we conclude that $(y_n)$ converges to $y$.   However, my friend does not think that this is completely correct because I didn't use the $y_{3n}$ in the proof. I think he is right, that I do in fact need it, but I am unsure of how to add it in. All in all, I think that since any term in the original sequence will be in one of these subsequences, it follows that the entire sequence $(y_n)$ converges to $y$.  $2n+1$ covers all the odd terms and $2n$ converse all the even terms, so is $3n$ even needed? I would like to use it since the proof has it in the question, but I am unsure of what to do. Could someone kindly help me construct this proof in a better manner,and is my line of thinking correct? Thank you!
81424
Given reals $a_1, a_2, \cdots, a_{n - 1}, a_n$ such that $a_1^2 + a_2^2 + \cdots + a_{n - 1}^2 + a_n^2 = 1$ $(n \in \mathbb N, n \ge 3)$. Calculate the maximum value of $$\large |a_1 - a_2| + |a_2 - a_3| + \cdots + |a_{n - 1} - a_n| + |a_n - a_1|$$   There must exist $1 &lt; k &lt; n$ such that $a_{k - 1} \le a_k \le a_{k + 1}$  $ \implies |a_{k + 1} - a_k| + |a_k - a_{k + 1}| = |a_{k + 1} - a_{k + 1}|$.  Repeat the above process for about $n - 1$ times and we have that $$|a_1 - a_2| + |a_2 - a_3| + \cdots + |a_{n - 1} - a_n| + |a_n - a_1| \le 2 \cdot \min(|a_i - a_j|, 1 \le i &lt; j \le n)$$  Now we just have to find the maximum value of $\min(|a_i - a_j|, 1 \le i &lt; j \le n)$ for $$a_1^2 + a_2^2 + \cdots + a_{n - 1}^2 + a_n^2 = 1$$, which I don't know how.
10678
I am preparing for Putnam and working through practice-like questions and I am boggled. I've got the sequence defined by $a_1 = 1$ and $a_{n+1} = 2a_n+\sqrt{3a_n^2-2}$ for any $n\in\mathbb{N}$ and I'm trying to show that every term is a positive integer. I am getting as far as  $a_{n+1}^2 -4a_{n+1}a_n + a_n^2 = -2$ but I can't figure out how to use the recursive relationship to show that all terms are integers. I've tried expanding the sequence in terms of $a_n$ or $a_{n+2}$ but it doesn't seem to get me far. Any hints or help would be greatly appreciated.
14885
I ran into nice problem which I proved and would be thankful if anyone assess it.  Given a sequence of integers $x_1,  x_2, \dots, x_n$ whose sum is 1? prove that exactly one of the cyclic shifts  $$x_1,x_2,\dots, x_n; \quad x_2,\dots, x_n,x_1; \cdots  \quad x_n, x_1\dots, x_{n-1}$$ has all of his partial sums positive. (By a partial sum we mean the sum of the first $k$ terms, $k\leqslant n$.)  My solution: For $n=1$ we have a single-term sequence and it is obvious.  Assume that our proposition is true for $n$. We'll try to prove it for $n+1$.  Let we have the sequence $(x_1, x_2, \dots, x_n,x_{n+1})$ then $\exists \ i$ such that $x_i&gt;0$.   If $1\leqslant i &lt;n+1$ then consider the following sequence $(x_1, \dots,x_i+x_{i+1},\dots, x_{n+1})$ which has $n$ elements. Then using the assumption of induction we have that there is exactly one cyclic shift with desired property, And if we write $x_i, x_{i+1}$ instead of $x_i+x_{i+1}$ and since $x_i&gt;0$ we get our desired sequence. If $i=n+1$, i.e. $x_{n+1}&gt;0$ then replace the sequence $(x_1, x_2, \dots, x_n,x_{n+1})$ by $(x_2, \dots, x_n,x_{n+1}+x_1)$ which consists of $n$ terms. Then using the assumption of induction we get exactly one sequence with desired properties and separating $x_{n+1}+x_1$ to $x_{n+1}, x_1$ we get the sequence with $n+1$ elements since $x_{n+1}&gt;0$.
47364
Note: I don't want to get the full solution, but only a hint.  I have to show that for $x \in [0, \infty)$, the sequence $\left(1+\frac xk\right)^k$ is monotonically increasing. We were already given the hint that we could use the inequality of arithmetic and geometric means, but I don't see how to apply it yet.   I tried to do it by induction. While the case $k = 1$ works easily, I don't know how to start further from here. I already tried to use the definition of the binomial theorem, but it didn't lead me anywhere.