0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – ashley Dec 15 '12 at 1:00
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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