Proof Problems

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.

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.

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

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$.

$\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.