Found problems: 30
Let $p$ be a prime number and $n, k$ and $q$ natural numbers, where $q\le \frac{n -1}{p-1}$ should be. Let $M$ be the set of all integers $m$ from $0$ to $n$, for which $m-k$ is divisible by $p$. Show that $$\sum_{m \in M} (-1) ^m {n \choose m}$$ is divisible by $p^q$.
For each positive integer $k$, we define the polynomial $S_k(x)=1+x+x^2+x^3+...+x^{k-1}$
Show that $n \choose 1$ $S_1(x) +$ $n \choose 2$ $S_2(x) +$ $n \choose 3$ $S_3(x)+...+$ $n \choose n$ $S_n(x) = 2^{n-1}S_n\left(\frac{1+x}{2}\right)$
for every positive integer $n$ and every real number $x$.
Let $p$ be a prime number. The natural numbers $m$ and $n$ are written in the system with the base $p$ as $n = a_0 + a_1p +...+ a_kp^k$ and $m = b_0 + b_1p +..+ b_kp^k$. Prove that
$${n \choose m} \equiv \prod_{i=0}^{k}{a_i \choose b_i} (mod p)$$
Let $k \le n$ be positive integers and $x$ be a real number with $0 \le x < 1/n$. Prove that
$${n \choose 0} - {n \choose 1} x +{n \choose 2} x^2 - ... + (-1)^k {n \choose k} x^k > 0$$
Let $n$ be a positive integer. Show that
$${2n+1 \choose 1} -{2n+1 \choose 3}2008 + {2n+1 \choose 5}2008^2- ...+(-1)^{n}{2n+1 \choose 2n+1}2008^n $$ is not divisible by $19$.
For each positive integer $n$, define $s(n) =\sum_{k=0}^n r_k$, where $r_k$ is the remainder when $n \choose k$ is divided by $3$. Find all positive integers $n$ such that $s(n) \ge n$.
Malik Talbi
For each positive integer $k$, denote by $P (k)$ the number of all positive integers $4k$-digit numbers which can be composed of the digits $2, 0$ and which are divisible by the number $2 020$. Prove the inequality $$P (k) \ge \binom{2k - 1}{k}^2$$ and determine all $k$ for which equality occurs.
(Note: A positive integer cannot begin with a digit of $0$.)
(Jaromir Simsa)
Let $n\ge 3$ be an integer and let $K_n$ be the complete graph on $n$ vertices. Each edge of $K_n$ is colored either red, green, or blue. Let $A$ denote the number of triangles in $K_n$ with all edges of the same color, and let $B$ denote the number of triangles in $K_n$ with all edges of different colors. Prove
\[ B\le 2A+\frac{n(n-1)}{3}.\]
(The [i]complete graph[/i] on $n$ vertices is the graph on $n$ vertices with $\tbinom n2$ edges, with exactly one edge joining every pair of vertices. A [i]triangle[/i] consists of the set of $\tbinom 32=3$ edges between $3$ of these $n$ vertices.)
[i]Proposed by Ankan Bhattacharya[/i]
Find all polynomials $P$ such that
$P(x) + \binom{2018}{2}P(x+2)+...+\binom{2018}{2106}P(x+2016)+P(x+2018)=$
$=\binom{2018}{1}P(x+1)+\binom{2018}{3}P(x+3)+...+\binom{2018}{2105}P(x+2015)+\binom{2018}{2107}P(x+2017)$
for all real numbers $x$.
Let $n$ and $k$ be positive integers. Evaluate the following sum
$$\sum_{j=0}^k\binom kj^2\binom{n+2k-j}{2k}$$where $\binom nk=\frac{n!}{k!(n-k)!}$.
Let $\{a_n\}^\infty_{n=0}$ be the sequence of integers such that $a_0=1$, $a_1=1$, $a_{n+2}=2a_{n+1}-2a_n$. Decide whether
$$a_n=\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}\binom n{2k}(-1)^k.$$
Find all primes $p$ such that ${100 \choose p} + 7$ is divisible by $p$.
Prove that, for all pairs of nonnegative integers, $j,n$, $$\sum_{K=0}^{n}k^j\binom n k \ge 2^{n-j} n^j$$
Find the coefficient of the fourth term of the expansion of $(x+y)^{15}$.
Let $n$ be a positive integer. Determine the smallest value of the sum $a_1b_1+a_2b_2+...+a_{2n+2}b_{2n+2}$
where $(a_1,a_2,...,a_{2n+2})$ and $(b_1,b_2,...,b_{2n+2})$ are rearrangements of the binomial coefficients $2n+1 \choose 0$, $2n+1 \choose 1$,...,$2n+1 \choose 2n+1$. Justify your answer
Prove the following equality for all positive integers $m,n$:
$$\sum_{k=0}^{n} {m+k \choose k} 2^{n-k} +\sum_{k=0}^m {n+k \choose k}2^{m-k}= 2^{m+n+1}$$
Let $x^{(n)}=x(x-1)\cdots (x-n+1)$ for $n$ a positive integer and let $x^{(0)}=1.$ Prove that
$$(x+y)^{(n)}= \sum_{k=0}^{n} \binom{n}{k} x^{(k)} y^{(n-k)}.$$
For each integer $n > 3$ find all quadruples $(n_1,n_2,n_3,n_4)$ of positive integers with $n_1 +n_2 +n_3 +n_4 = n$ which maximize the expression $$\frac{n!}{n_1!n_2!n_3!n_4!}2^{ {n_1 \choose 2}+{n_2 \choose 2}+{n_3 \choose 2}+{n_4 \choose 2}+n_1n_2+n_2n_3+n_3n_4}$$
Find all positive integers $x$ and $y$ such that $${x \choose y} = 1432$$
Find all positive integers $k$ for which there are infinitely many positive integers $n$ such that $\binom{(2025+k)n}{2025n}$ is not divisible by $kn+1$.
Let $\{x_n\}^\infty_{n=0}$ be the sequence such that $x_0=2$, $x_1=1$ and $x_{n+2}$ is the remainder of the number $x_{n+1}+x_n$ divided by $7$. Prove that $x_n$ is the remainder of the number
$$4^n\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}2\binom n{2k}5^k$$
If the coefficient of the third term in the binomial expansion of $(1 - 3x)^{1/4}$ is $-a/b$, where $ a$ and $b$ are relatively prime integers, find $a+b$.
Let ${n \choose k}$ be the number of ways that $k$ objects can be chosen (regardless of order) from a set of $n$ objects. Prove that if positive integers k and l are greater than $1$ and less than $n$, then integers ${n \choose k}$ and ${n \choose l}$ have a common divisor greater than $1$.
If $$s_n = 1 + q + q^2 +... + q^n$$ and $$ S_n = 1 +\frac{1 + q}{2}+ \left( \frac{1 + q}{2}\right)^2 +... + \left( \frac{1 + q}{2}\right)^n,$$ prove that $${n + 1 \choose 1}+{n + 1 \choose 2} s_1 + {n + 1 \choose 3} s_2 + ... + {n + 1 \choose n + 1} s_n = 2^nS_n$$
Observe that the number $4$ is such that $4 \choose k$ $= \frac{4!}{k!(4-k)!}$ divisible by $k + 1$ for $k = 0,1,2,3$. Find all the natural numbers $n$ between $50$ and $90$ such that $n \choose k$ is divisible by $k + 1$ for $k = 0,1,2,..., n - 1$. Justify your answers.