# Proof Problems

Here I list some problems,which I got while practicing. Help is solicited. Thanks. (The discussion has been updated, you may check out the comments for the previous problems I posted)

1. Prove that given any prime $$p$$, there exist infinitely many positive integers $$n$$, such that $$p| n2^{n-1}+1$$.

2. If every point of the plane is painted one of three colors, do there necessarily exist two points of the same color exactly one inch apart?

3. Let $$n>1$$ is an odd integer. Show that the sequence

$$\displaystyle {n \choose 1},{n \choose 2},...,{n \choose \frac{n-1}{2}}$$ has an odd number of odd integers.

Note by Paramjit Singh
4 years, 9 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

• bulleted
• list

1. numbered
2. list

1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

> This is a quote
This is a quote
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

1. We have $$3n+1 = a^2$$, and so $$3n = (a-1)(a+1)$$. There are two cases to consider. If $$3$$ divides $$a-1$$, then $$a = 3m+1$$, so $$n = m(3m+2)$$, and hence $$n+1 = 3m^2 + 2m + 1 = m^2 + m^2 + (m+1)^2$$. If $$3$$ divides $$a+1$$ then $$a = 3m+2$$, so $$n = (3m+1)(m+1)$$, and hence $$n+1 = 3m^2 + 4m + 2 = m^2 + (m+1)^2 + (m+1)^2$$.

2. The sum of the numbers from $$1$$ to $$50$$ is $$1275$$, which is odd. Thus if $$A$$ is any subset of $$\{1,2,\ldots,50\}$$ and $$A' = \{1,2,\ldots,50\} \backslash A$$ is its complement, then the sum of the elements in $$A$$ and the sum of the elements in $$A'$$ together add to the odd number $$1275$$, and hence one must be even and the other odd. Thus the operation of complementation is a bijective map from the set of subsets of $$\{1,2,\ldots,50\}$$ with odd sum to the set of subsets of $$\{1,2,\ldots,50\}$$ with even sum. Since there are $$2^{50}$$ subsets of $$\{1,2,\ldots,50\}$$, exactly half of them, namely $$2^{49}$$, have an odd sum.

- 4 years, 9 months ago

Perfect. Thank you sir. Can't believe these proofs were so trivial.

- 4 years, 9 months ago

Doesn't the result in problem $$2$$ follow directly from symmetry?

EDIT: Never mind, your proof is a more rigorous version of mine. :)

- 4 years, 9 months ago

1. Multiply out by $$x(x+1)(x+2)\cdots(x+n)$$ and put $$x=-k$$ to evaluate $$A_k$$.

2. If $$A,B,C$$ are odd integers and $$\tfrac{a}{b}$$ is a root of $$AX^2 + BX + C = 0$$, where $$a,b$$ are coprime integers, then $$Aa^2 + Bab + Cb^2 = 0$$. But since $$A,B,C$$ are all odd and $$a,b$$ are coprime (and so not both even) $$Aa^2 + Bab + Cb^2$$ must be odd, giving you a contradiction.

- 4 years, 9 months ago

Thanks. Nice solution to both $$(1)$$ & $$(2)$$.

- 4 years, 9 months ago

$\text{#}2$ From symmetry one can conclude that the number of subsets with odd sum of elements is equal to the number of subsets with even sum of elements. Since there are a total of $$2^{50}$$ subsets, it immediately follows that there are $$2^{49}$$ subsets with odd element sum.

EDIT: @Paramjit I used that idea. I'm sorry, I just provided a bare sketch of a proof.

- 4 years, 9 months ago

Mark H. has used the same basic idea perfectly. You need to show that sum of the numbers from $$1$$ to $$n$$ is odd, here, else your proof is not complete. (In general, it is easy to know from Mark's solution that "If $$n = 2k = k +k$$ is even, number of odd-sum subsets outnumbers the even-sum subsets when $$k$$ is odd & opposite when $$k$$ is even (as $$n = 4k' = 2k'+2k'$$).")

- 4 years, 9 months ago

Some previous problems:- (As such, Mark H. & Siddhartha S. have already given perfect solutions to these.)

1. In the identity $$\frac{n!}{x(x+1)(x+2)...(x+n)} = \displaystyle \sum_{k=0}^n \frac{A_k}{x+k}$$, prove that: $$A_k = (-1)^k {n \choose k}$$.

2. If the coefficients of a quadratic equation are all odd integers, show that its roots can not be rational.

3. Show that the number $$11...11$$ with $$3^n$$ digits is divisible by $$3^n$$.

4. For a natural number $$n$$, let $$a_n = n^2 + 20$$. Show that $$\gcd(a_n,a_{n+1}) | 81$$.

5. Show that if a prime number is divided by $$30$$, then the remainder is either a prime or $$1$$.

- 4 years, 9 months ago

1. The fact will follow from Lemma: if $$n$$ is not a perfect square then $$\sqrt{n}$$ is irrational. Proof: suppose $$\frac{i^{2}}{j^{2}} = n$$ if $$p|i$$ $$p$$ a prime then $$p^{2}|n$$. Hence $$i^{2}|n \Longrightarrow 1 = \frac{nj^{2}}{i^{2}} \Longrightarrow \frac{n}{i^{2}} = j^{2} = 1$$ because $$n,i,j$$ are positive integers and $$i^{2}|n$$.
Now the problem is equivalent to showing that $$b^{2} - 4ac$$ is not a perfect square. Because $$ac$$ is odd $$b^{2} - 4ac$$ is congruent to $$b^{2} + 4$$ modulo $$8$$. But because $$b$$ is odd $$b^{2} = 1 + 8k \Longrightarrow b^{2} - 4ac = 5 + 8k$$ witch is not a perfect square because $$5$$ is not a quadratic residue $$(mod8) Q.E.D$$

- 4 years, 9 months ago

EDIT: this is for problem 2 not 1.

- 4 years, 9 months ago

3.

Base Case : When $$n = 1$$;

$$111$$ is divisible by $$3$$.

Inductive Case : If $$11\ldots11$$ with $$3^n$$ digits is divisible by $$3^n$$,

For n+1, $$11\ldots11$$ with $$3^{n+1}$$ digits

$$= 11\ldots11 + 11\ldots1100\ldots00 + 11\ldots1100\dots00$$

With the first term having $$3^n$$ 1's, the second term $$3^n$$ 1's and 0's, and the last term with $$3^n$$ 1's and $$2 * 3^{n}$$ 0's.

$$= 11\dots11(1 + 10^{3^n} + 10^{2*3^n})$$

$$= 11\dots11(10\dots010\dots01)$$

The first part is divisible by $$3^n$$ and the second by $$3$$. Therefore, their product is divisible by $$3^{n+1}$$

4.

$$\gcd( n^2 + 20, n^2 + 2n + 21)$$

Subtracting the first term from the second,

$$= \gcd( n^2 + 20, 2n + 1)$$

Multiplying the first term with 4 won't change the gcd since 2n + 1 is odd.

$$= \gcd( 4n^2 + 80, 2n + 1)$$

Dividing the first term by the second

$$= \gcd( 81,2n+1)$$

Since the gcd is the greatest common DIVISOR of 81 and 2n + 1, it will divide 81.

5.

Applying the Euclidean Division lemma to p and 30, we get,

$$p = 30q + r, 0 \leq r < 30$$

If r is divisble by 2,3 or 5, It would imply p is divisible by 2,3 or 5, which is not possible. Therefore r is not divisible by 2,3 or 5.But every composite number below 30 contains a factor of 2,3 or 5. Therefore r is prime or equal to 1

- 4 years, 9 months ago

Awesome! Check back for some updates to this thread. I myself got Q4 2 hours after I posted. Thanks!

Typo: 7th line end: It should be $$2*3^n$$ 0's,

- 4 years, 9 months ago

Thanks. Corrected.

- 4 years, 9 months ago