Tagged Questions
1
vote
1answer
46 views
Combinatorics identity sum of
Prove that:
$$\sum^{n}_{k=0}\binom{k}{2n-k}2^k = 2^{2n}$$
By using only combinatorics identities.
3
votes
1answer
38 views
Proving that $n|m\implies f_n|f_m$
Question: Let $m,n\in\mathbb{N}$, prove that if $n|m$, $F_n|F_m$.
I've tried to use induction, but I don't really know where to start since there's $2$ numbers: $n$ and $m\ \dots$ I did induction ...
2
votes
3answers
106 views
combinatorial argument and by induction proof
Let n be a fixed natural number. Show that:
$$\sum_{r=0}^m \binom {n+r-1}r = \binom {n+m}{m}$$
(A): using a combinatorial argument and (B): by induction on $m$?
3
votes
3answers
82 views
Induction proof of $\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$
Does anynone have some hints to prove the following equation by induction for all $n\geq 1$ and $m\in\mathbb{Z} $
$$\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$$
use for ...
4
votes
1answer
90 views
In the marriage problem, if each girl knows at least $m$ boys, then there are at least $m!$ ways to arrange the marriages.
I'm finding problems concerning Hall's theorem very difficult even when they're not. (See here for example. I'm sure I wouldn't have come up with the solution in a million years even though it's ...
0
votes
4answers
88 views
Conjecture to start a proof
In an inductive proof example, my book starts with the identity stating $$\sum\limits_{i=1}^n \sum\limits_{j=1}^i j = \frac{n(n+1)(n+2)}{6}\;.$$ As a sidenote, it says they reached this identity by ...
1
vote
0answers
50 views
Mathematical Induction and the Fundamental Theorem of Arithmetic
Prove if $n$ is an integer, $n \geq 2$, then either $n$ is prime or else can be factored into a product of primes.
I don't quite understand (at all) how to connect this to the fundamental theorem of ...
0
votes
3answers
79 views
Mathematical Induction & Proof of “Twelve Days of Christmas” Formula
Conjecture and prove a formula for $$\sum\limits_{i=1}^n\sum\limits_{j=1}^i j.$$ Note when $n=12$ the sum equals the total number of gifts given in the "twelve days of xmas" song.
0
votes
2answers
141 views
1000 doors, few keys as possible problem
I haven't dealt with college level math in a little while, so forgive me if this is a little trivial. It feels like it has something to do with the birthday paradox...but the opposite.
Any help at ...
4
votes
2answers
261 views
Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$
I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$
I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
0
votes
0answers
51 views
proving an inequality by induction
Not sure how to proceed. I'm trying to prove that the following inequality is true. I know that $t_2 = 6$ and $t_3=17$ from the problem statement. The base case is obvious.
$t_{r+1} \leq (r+1) (t_r ...
4
votes
0answers
115 views
Efficiently count possible nim-like moves
Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, ...
2
votes
5answers
110 views
Induction on binomial Identity
I am having trouble proving the following identity:
$0\cdot {n\choose 0} + 2\cdot {n\choose 2} + 4\cdot {n\choose4}+\ldots = n\cdot2^{n-2}$
Here is what I have so far:
Proof:
Base: Let $n=0$:
...
0
votes
2answers
117 views
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
...
2
votes
2answers
84 views
Prove the following relation:
I must prove the relation $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}.$$
I got this far before I got stuck:
$\begin{eqnarray*}
...
3
votes
4answers
149 views
How to prove if function is increasing
Need to prove that function $$P(n,k)=\binom{n}{k}= \frac{n!}{k!(n-k)!}$$ is increasing when $\displaystyle k\leq\frac{n}{2}$.
Is this inductive maths topic?
4
votes
1answer
117 views
Generating function of Lah numbers
Let $L(n,k)\!\in\!\mathbb{N}_0$ be the Lah numbers. We know that they satisfy
$$L(n,k)=L(n\!-\!1,k\!-\!1)+(n\!+\!k\!-\!1)L(n\!-\!1,k)$$
for all $n,k\!\in\!\mathbb{Z}$. How can I prove
...
0
votes
1answer
99 views
Algebra on $\binom{k+1}{i} = \binom{k+1}{0} + \binom{k+1}{1} + \cdots + \binom{k+1}{k} + \binom{k+1}{k+1}$ [duplicate]
Possible Duplicate:
Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$
I am trying to prove $\sum \limits_{i=0}^n \binom{n}{i} = 2^n$ by induction. I've been all over the net ...
3
votes
3answers
2k views
Proving that $|xy| = |x| + |y|$ being $x$ and $y$ two strings
I am to prove that being $x$ a string and $|x|$ its length, one should have the following property hold true for any two strings $x$ and $y$:
$$ |xy| = |x| + |y| $$
with $x, y \in \Sigma^*$.
To ...
