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

  • 0
    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}$.2012-12-15

2 Answers 2

3

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

0

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