# 3 Homework Question. Counting, Induction and Pigeonhole principle

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

Question-2:

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.

Question-6:

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

Question-7:

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

• 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

(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?