Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

First hello all. i have a homework with 10 question but im stuck with 3 i searched about them everywhere read other colleges lectures but i couldnt solved them finally i desired to ask here


Prove that each positive integer can be written in form of $2^k*q$, where q is odd, and k is a non-negative integer.

Hint: Use induction, and the fact that the product of two odd numbers is odd.


$$ (x+y)^n = \sum_{k=0}^n C(n,k)*x^{n-k}*y^k = {n^2+n\over 2} $$ Prove the above statement by using induction on n.


Let $ n_1, n_2, ..., n_t $ be positive integers. Show that if $ n_1 + n_2 + ... + n_t - t + 1 $ objects are placed into $ t $ boxes, then for some i, $ i = 1, 2, 3, ... , t $ , the ith box contains at least $ n_i $ objects.

Your proof should not be more than 3 lines

share|cite|improve this question
Intuition-- for Q2: Try to come up with an even number that doesn't have 2 as its divisor. For Q7: try a placement with $n_{i}-1$ objects at each $n_{i}$. – ashley Dec 15 '12 at 1:00
up vote 3 down vote accepted

(2) Certainly we can write $1=2^0\cdot1$. Now suppose that $n>1$, and every positive integer less than $n$ can be written in the desired form. (This is your induction hypothesis.) Then either $n$ is odd, or $n$ is even. If $n$ is odd, we can write $n=2^0\cdot n$ to express $n$ in the desired form. If $n$ is even, then $n=2m$ for some positive integer $m<n$. By the induction hypothesis there are a non-negative integer $k$ and an odd integer $q$ such that $m=2^k\cdot q$; how can you use this to express $n$ in the desired form? (This is not quite the proof that the author of the hint had in mind; it’s actually a bit easier.)

(6) As stated, this does not make sense. It’s true that $$(x+y)^n=\sum_{k=0}^n\binom{n}kx^{n-k}y^k\;;$$ this is the binomial theorem. It is not true that this equals $\dfrac{n^2+n}2$; this is obvious just from the fact that $\dfrac{n^2+n}2$ doesn’t depend on $x$ and $y$. What is true is that $$\sum_{k=0}^nk=\frac{n^2+n}2\;;$$ is this what you’re actually supposed to prove?

(7) Let $m_i$ be the number of objects in the $i$-th box, and suppose that $m_i<n_i$ for $i=1,\dots,t$. Then $m_i\le n_i-1$ for $i=1,\dots,t$, so how big can $\sum_{i=1}^tm_i$ be?

share|cite|improve this answer

(2) For the hint the author probably had in mind: think about prime factorizations of positive integers.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.