I can use either combinatorial argument, or mathematical induction on ${n+1\choose k} = {n\choose k}+{n\choose k-1}$ to prove $\prod_{i=0}^{k-1}(n-i)$ being divisible by $k!$ or that $n \choose k$ is a natural number for natural numbers $n$ and $k$. What is a number theoretical proof for it that does not use mathematical induction? Please do not give me a combinatorial argument with which I am infinitely familiar!
12113
How can we prove, without using the properties of binomial coefficients, the product of $n$ consecutive integers is divisible by $n$ factorial?
104668
I need to prove this $$\sum_{k=0}^n \binom{n+k}{k}=\binom{2n+1}{n}$$ Using induction and basically only the Pascal's identity and the symmetry property for binomial coefficients. Now, I noticed that $\sum_{k=0}^n \binom{r+k}{k}=\binom{r+n+1}{n}$ has a relatively simple proof by induction and it basically holds for any $r$. Could I apply that property for $r=n$ and call it a day? I also tried to solve the problem by using a similar argument, the induction step however states that $$\sum_{k=0}^{n+1} \binom{n+1+k}{k}=\sum_{k=0}^{n} \binom{n+1+k}{k}+\binom{2n+2}{n+1}$$ then $$\sum_{k=0}^{n+1} \binom{n+1+k}{k}=\sum_{k=0}^{n} \binom{n+k}{k}+\sum_{k=0}^{n} \binom{n+k}{k-1}+\binom{2n+2}{n+1}$$ Using the induction hypothesis $$\sum_{k=0}^{n+1} \binom{n+1+k}{k}= \binom{2n+1}{n}+\sum_{k=0}^{n} \binom{n+k}{k-1}+\binom{2n+2}{n+1}$$ And that's where I got stuck. Is this a dead end?
92798
So the statement is:  Prove: $$F^2_{n+1} - F^2_{n-1} = F_{2n}$$  How could this be proven with induction?  What about without induction?  For induction I got here: (already tested $n=1$, and assumed $n=k$ held true)  $$F^2_{k+2} - F^2_{k} = F_{2k + 2}$$ $$(F_{k+1} + F_{k})^2 - (F_{k-1} + F_{k-2})^2 = F_{2k+1} + F_{2k}$$ Then you get some cancelation based off the $n=k$ case $$2F_{k+1}F_k + F_k^2 - 2F_{k-1}F_{k-2} - F_{k-2}^2 = F_{2k+1}$$  This is where I am stuck for the induction proof.  I have no idea where to begin with the non-induction proof.
23389
Proof that $\suṃ̣_{k=1}^{n}k {n \choose k}$ for $n \in \mathbb N$ is equal to $n2^{n-1}$.  As a hint I got that $k {n \choose k} = n {n-1\choose k-1} $.  I tried solving this by induction but, in the inductive step I'm not arriving to the correct result.
75668
I have trouble coming up with combinatorial proofs. How would you justify this equality?  $$ n\binom {n-1}{k-1} = k \binom nk $$ where $n$ is a positive integer and $k$ is an integer.
106937
I can't figure out an algebraic proof for the following identity:  $$\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$$  Combinatorical solution:  We can see that as choosing some from $n$ and the rest of $k$ from $m$, thus $k$ in total.  Or we could just choose $k$ from the union.
18135
How do I prove that $3^n &gt; n^2$ with mathematical induction? I thought I had the correct answer but my teacher says its wrong.  I let $n=1$ for the initial case and it works. I then assumed $n=k$ works and went onto the $n=k+1$ case, but after that it goes a little awry. Thanks in advance!
44448
Given a set of $n+1$ numbers out of the first $2n$ natural numbers, $\{1,2,\ldots,2n\}$, prove that there are two numbers in the set, one of which divides the other.  I can't tell if I'm reducing the problem in the right way.  Would it be something like:  Induction Hypothesis: A set of $n+1$ numbers from the first $2n$ natural numbers contains two numbers, one of which evenly divides the other.  Base Case: $n=1$, $\{1,2\}$, 2 is divisible by 1.  Consider a set of $n+2$ numbers, $A$, from the first $2n+2$ natural numbers. There are three cases:   Each number in $A$ is less than or equal to $2n$.  The proof follows from the induction hypothesis. One number in $A$ is greater than $2n$.  The remaining set of $n+1$ numbers must each be less than or equal to $2n$.  The proof follows from the induction hypothesis. $A$ contains both $2n+1$ and $2n+2$. I'm not sure how to solve this case.   I'm working through Udi Manber's Introduction To Algorithms: A Creative Approach for personal development, so in keeping with the spirit of the book, I'm trying to use induction.  Without induction, the question is identical to
101451
So I need to use induction to prove that $4^n&lt;5^n$ for all natural numbers $n &gt; 0$. I have proved the base case to be true. For the induction hypothesis, we assume that when $n=k$, then $4^k &lt; 5^k$. However, I am stuck in the inductive step when I try to show that it needs to be true for $n+1$. Therefore, we need to show that $4^{k+1} &lt; 5^{k+1}$. However I get stuck on the first step trying to prove it as in  $4^{k+1} = 4 \cdot 4^k$, then by substituting $5^k$ instead of $4^k$ from the inductive hypothesis and I get stuck right here and I do not know how to proceed.  Any help would be appreciated.
49946
How do I prove the following statement by induction?  $$n^2 \lt 2^n$$  $P(n)$ is the statement $n^2 \lt 2^n$  Claim: For all $n \gt k$, where $k$ is any integer, $P(n)$  (since $k$ is any integer, I assume I have to prove this for positive and negative integers)  So let base case be $P(1)$, and I have to prove $P(n)$ for $n \ge 1$ and $n \lt 1$  $P(1)$ is $1^2 \lt 2^1$ which is clearly true.  Induction hypothesis: $k^2 \lt 2^k$  Inductive step $(k+1)^2 \lt 2^{(k+1)}$  $(k+1)^2 = k^2 + 2k + 1$  $k^2 + 2k + 1 \lt 2^k + 2k + 1$ by inductive hypothesis  Not sure how to proceed. Is my previous intuition that I have to prove this for $n \ge 1$ and $n \lt 1$ correct?
23149
For any natural number $n\ge 1$, given pairs $(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$ of integer numbers, there exist integer number $c$ and $d$ such that  $$\prod_{i=1}^{n}(a_i^2+b_i^2) = c^2+d^2$$    My initial approach is  Base Case: $(a_1^2+b_1^2) = a_1^2+b_1^2$ which is true. (Although it is trivial)  Prove the statement is true when $n=2$: We have $$(a^2+b^2)(c^2+d^2) = (ac-bd)^2+(ad+bc)^2$$ (Thanks André Nicolas for pointing it out)   So if $a,b,c,d$ are integers, $ac,bd,ad,bc$ are all integers and integers are closed under addition and subtraction. Hence $(ac-bd),(ad+bc)$ are integers.   Inductive Hypothesis: $\prod_{i=1}^{n}(a_i^2+b_i^2) = c^2+d^2$ is true  Inductive Step: $$\prod_{i=1}^{n+1}(a_i^2+b_i^2) = \prod_{i=1}^{n}(a_i^2+b_i^2)\cdot (a_{n+1}^2+b_{n+1}^2) = (c^2+d^2)\cdot (a_{n+1}^2+b_{n+1}^2)$$  Where $c$ and $d$ are integers.   But when we apply $n=2$, we have  $(c^2+d^2)\cdot (a_{n+1}^2+b_{n+1}^2) = (e^2 + f^2)$ where $e$ and $f$ are integers.  Hence, by the principle of induction, the statement we needed to prove is true.
44709
I'm trying to prove using induction that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a non-negative integer. So far, I have:   Base case: $P(1) = (1) + (8) + (27) = 36, 36$ can be divided by $9$ so the base case is valid Inductive step: let $P(n)$ be the statement $9$ divides $n^3 + (n+1)^3 + (n+2)^3$. Assume $P(k)$ is true, so $9$ divides $k^3 + (k+1)^3 + (k+2)^3$.   And this is where I'm stuck. I'm not sure how to demonstrate that $9$ divides $P(n)$ when $n = k+1$. If someone could step me in the right direction that would be awesome. Thanks!
12205
Prove by induction: Find a, and prove the postulate by mathematical induction.  $$\text{For all}~ n &gt; a,~ n! &gt; n^3$$  Where ! refers to factorial.  So far I've done a bit of it, I'll skip right to the inductive statement and assume that $k! &gt; k^3$, then try to prove $(k+1)! &gt; (k+1)^3$  Inductive statement: $(n+1)! &gt; (n+1)^3$  $(n+1)^3= n^3 + 3n^2 + 3n + 1 &lt; n! + 3n^2 + 3n + 1$ (By Induction Hypothesis)  ...But now I'm stuck. Does anyone know where to go next?
90968
Must show:     $\sum_{i=0}^n i{n \choose i} = n2^{n-1}$ using a combinatorial argument. I have tried picking the problem apart by determining that the summation is equal to 1/2 of the size of all subsets of a set of size n times n.  But I am having trouble relating that to what each term of the summation represents.
52936
Use  strong mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes.    I know the steps of weak mathematical induction... Basis step: $p(n)$ for $n=1$ or any arbitrary $n_0$ ... show that it is true Inductive hypothesis: $p(n)$ for $n=k$ ... Assume that it is true for $n=k$ Inductive step: $P(n)$ for $n=k+1$ ... Show that this is true for $n=k+1$
58852
has the identity $$S(n+1, k+1) = \sum_i {n \choose i} S(i, k)\;.$$ I can't seem to find a proof for this and was wondering what it entails. Is it a purely combinatoric argument, or an algebraic manipulation of the explicit formula $S(n, k) = \frac{1}{k!} \sum_{i=0}^k (-1)^i {k \choose i}(k-i)^n $ with the known recurrence formula $S(n+1, k+1) = S(n, k) + (k+1)S(n, k+1)? $
25521
I need to prove by induction if ${n^5 - n}$ is divisible by 5 and I have no idea how I would do it.   I am trying to prove it for several hours now, I started with ${n^5 - n} \mod  5 = 0$ but then I realized that I have no idea how to use modulo for transformations.  The next thing I tried was $(5 + n)\frac{n^5 - n}5 = \frac{(n+1)^5 - n+1}5$ but it didn't get me anywhere.  How would you do it?