Inductioning....

Filed on Sun Apr 23, 2006 11:09 pm, by xxreddevilzxx

Prove that if $x+\frac{1}{x} \in \mathbb{Z}$ for some $x \in \mathbb{R}$ , then $x^n+\frac{1}{x^n} \in \mathbb{Z}$ for any $n \in \mathbb{N}$

We see that this problem requires some sort of induction (or shall i say it is easier to do induction Mr. Green

) since we have the inductive case. (in this case when $n=1$ )

Then assume that it is true for $n=k$ and $n=k-1$

Then $x^{k+1}+\frac{1}{x^{k+1}} = \left(x^k+\frac{1}{x^k}\right) \left(x+\frac{1}{x}\right) - \left(x^{k-1}+\frac{1}{x^{k-1}}\right...$

Since all the terms in the equation are real, then it is also real in $k+1$ and we are done.

Prove that $1 < \frac{1}{n+1} + ... + \frac{1}{3n+1} < 2$

First, $LHS$ :
$n=1$ yields $\frac{1}{2}+\frac{1}{3}+\frac{1}{4} = \frac{13}{12} > 1$
Then if it holds true for some $n=k$ then
$f(k+1) = f(k) - \frac{1}{k+1} + \frac{1}{3k+2} + \frac{1}{3k+3} + \frac{1}{3k+4}$

Thus it is sufficient to show that $\frac{1}{3k+2} + \frac{1}{3k+3} + \frac{1}{3k+4} > \frac{1}{k+1}$ .

$\frac{1}{3k+2} + \frac{1}{3k+3} + \frac{1}{3k+4} > \frac{1}{k+1} \Leftrightarrow \frac{1}{3k+2} + \frac{1}{3k+4} > \fra...$ .

The latter is true since:

$\frac{1}{3k+2} + \frac{1}{3k+4} = \frac{6n+6}{\left(3n+2\right) \left(3n+4\right)} > \frac{6n+6}{\left(3n+3\right)^2} = \f...$

Now, $RHS$ :
$\frac{1}{n+1} + ... + \frac{1}{3n+1} < \frac{1}{n+1} + ... + \frac{1}{n+1} = \frac{2n+1}{n+1} <2$ So this was trivial, and no need for an induction. And so we are done. $QED$

---------------------------------------------------------
Induction is a tool that allows you to prove something far more difficult given a base case, usually $n=1$ that is trivial. Induction is thus a very useful tool in proving formulas that are very difficult or time-consuming to prove straight forward, such as Binet's formula or Pascal's triangle properties.

ENUMERATIVE

Filed on Sat Apr 22, 2006 9:26 pm, by xxreddevilzxx

Source: 1977 Belgrade Olympiad (listed in Engel's)
In a finite sequence of real numbers, every 7-sum is negative, whereas every 11-sum is positive. Find the greatest number of terms in such a sequence

At first this problem seems hard. There aren't very many distantly related problems to this, but it is very trivial once thought through.

solution
Write successive 7-sums in rows:
$a_1+a_2+a_3+a_4+a_5+a_6+a_7<0$
$a_2+a_3+a_4+a_5+a_6+a_7+a_8<0$
$a_3+a_4+a_5+a_6+a_7+a_8+a_9<0$
$a_4+a_5+a_6+a_7+a_8+a_9+a_{10}<0$
$a_5+a_6+a_7+a_8+a_9+a_{10}+a_{11}<0$
$a_6+a_7+a_8+a_9+a_{10}+a_{11}+a_{12}<0$
$a_7+a_8+a_9+a_{10}+a_{11}+a_{12}+a_{13}<0$
$a_8+a_9+a_{10}+a_{11}+a_{12}+a_{13}+a_{14}<0$
$a_9+a_{10}+a_{11}+a_{12}+a_{13}+a_{14}+a_{15}<0$
$a_{10}+a_{11}+a_{12}+a_{13}+a_{14}+a_{15}+a_{16}<0$
$a_{11}+a_{12}+a_{13}+a_{14}+a_{15}+a_{16}+a_{17}<0$

We see that adding by rows and summing up the results will give us negative result. However, if we sum up by rows, since all 11-sums are positive, the results should be positive. This contradicts each other, and that such desired sequence can have at most 16 terms. The construction of such sequence is not trivial, but also not un-doable:

$3,3,-8,3,3,3,-8,3,3,-8,3,3,3,-8,3,3$ gives us the desired 16-term sequence.

In every sequence of positive integers, each 17-sum is even and 18-sum is odd. How many terms can such a sequence have at most?

Applying the same method from above, we see that the sequence can have at most 33 terms. Coming up with a sequence of that one is even harder, and I have not come up with one yet Wink

In generalization, we see that for these types of problems, if we have sequences of length $p$ and $q$ such that $gcd(p,q)=1$ , then the maximal length of any sequence is given by $p+q-2$ . This is a famous and the most basic types of Enumerative Combinatorics, and was proved by John Rickard at the IMO. These problems belong to combinatorics, in a wider sense, and are hard to train for. However, once you see the trick, it is fairly easy.

A little Parity Check

Filed on Thu Apr 20, 2006 9:09 am, by xxreddevilzxx

Given a set of nonnegative integers from $1$ to $n$ , and some sort of permutation of that given $a_1, ..., a_n$ . If $n$ is odd, then prove that $(a_1-1)(a_2-2)....(a_n-n)$ is even.

We assume that it is not even. Then all the terms in the product have to be odd. Parity check reveals that in order to have a difference of an odd number the parity between two numbers being subtracted must be different. We have one more odd number than even, and when we match one odd number with one even number, we are left off with two odd numbers at the end, which should differ by an even number. Thus this contradicts the earlier statement, and in fact the product must be even.

This problem gave us the glimpse to use parity, since the problem asked to prove the parity of something.

Given points $P_1, P_2,...P_{999}$ , we connect two points with the line segments $P_1P_2, P_2P_3, ..., P_{999}P_1$ . Can we draw a line that passes through all these points?

This is a little complicated case of parity. It is not apparent that we should use parity, although the numbering of the points suggest that we should. So assume that there is a line that goes through all such line segments. Then that line divides the plane into two sides. WLOG, assume $P_1$ is on one of the side (left or right). Then that forces $P_2$ to be on the opposite sides, to satisfy the condition. Then $P_3$ must be on the same side with $P_1$ and so forth. It is then obvious that points are on the same side of the plane depending on the parity! Since $P_1$ and $P_{999}$ are on the same side of the plane, the line cannot go through $P_{999}P_1$ and thus that contradicts the statement.

This problem was a little difficult parity problem in that it did not specify or give a hint of parity at all. However, once you play around with it it is easier to find that parity does play a huge role.

Like the two problems above, parity can be a little thing; just odd and even. However, knowing that and knowing how to apply that to a problem can be huge.

Simple Pigeonhole-ing

Filed on Wed Apr 19, 2006 12:20 am, by xxreddevilzxx

In any $n+2$ integers, show that either there are two whose difference is multiple of $2n$ or two whose sum is divisible by $2n$ .

We see that those $n+2$ numbers in the set has to be $k\mod{2n}$ , for some integer $k \in {0,1....,2n-1}$

We see that there are pairings of those $\mod{2n}$ that can be added to be $0\mod{2n}$ , such as $(1, 2n-1), (2, 2n-2)...$ Since there are $n-1$ pairs of these ( $0$ and $n$ cannot be paired). However, since there are $n+2$ numbers three numbers must be in pair with its corresponding numbers in the set. Thus there are two whose sum is divisible by $2n$ .

We can do it likewise in a difference of two number. The theory behind this was using pigeonhole. The way this problem was set called for pigeonhole since it gave the pigeon ( $n+2$ -number set) and ask to prove "at least..."

questions... about AM-GM

Filed on Sun May 15, 2005 10:52 pm, by YSJeong

Although I am only in middle school, with my brother posting me as a contributor, I decided to ask him a question on this blog (since I dont want to PM him).

Prove that $a+3b \ge 4b\sqrt[4]{a}$
I tried using simply by plugging in numbers, but my brother had better things in mind: use AM-GM.

$a+3b \Leftrightarrow a+b+b+b \ge 4\sqrt[4]{abbb} \Leftrightarrow 4b\sqrt[4]{a}$ .

Here was another question:
Prove 3-term AM-GM knowing that you have already proven 4-term AM-GM.

I tried using substitution from this inequality

$\frac{a+b+c+d}{4} \ge \sqrt[4]{abcd}$

which is a 4-term AM-GM, to turn it into a 3-term AM-GM. However, I could not find any number to turn the 4th root into 3rd root, which will transform the $RHS$ . I got stuck again, and hopefully when my brother sees this, he can solve it, or prove it.

Having said all that, I thought the first problem was too obvious, and I dont get why I didnt see it at first. but then again, I am only a 7th grader, and knowing AM-GM is certainly more than any other fellow 7th graders can bear. Unless, of course if your name is either Nathan Benjamin or Neal Wu Mr. Green