0
votes
1answer
27 views

conjecture and prove set induction problem

Let $X_n$ = $\{1,2,3,4,\ldots,n\}$ (a set). Conjecture and prove that $\sum_{\emptyset \neq A\subseteq X_n}\frac{1}{p_A}=n$, where $p_A$ is the product of the subset. Attempt: $\sum_{\emptyset \neq ...
3
votes
0answers
26 views

Combinatorics, equality, $n$-permutations with $k$ cycles

Let $b_r(n,k)$ denote the number of $n$-permuations with $k$ cycles in which all numbers: $1,...,r$ are in one cycle. Prove that for $n \ge r$, $\sum _{k=1} ^n b_r(n,k) x^k = (r-1)! ...
1
vote
1answer
63 views

Prove $1! + 2! + . . . + n! < (n + 1)!$ using mathematical induction [duplicate]

$1! + 2! + . . . + n! < (n + 1)!$ This question has left me stumped for quite some time. I am not sure how to approach it. (I am really bad at induction).
33
votes
5answers
4k views

Prove that the 25 people can be seated in this way

5 mathematicians, 5 biologists, 5 chemists, 5 physicists, and 5 economists sit around a large round table. Prove that the 25 people can be seated such that, if A and B are two different people with ...
1
vote
1answer
40 views

Sum of nth powers and generalized polynomial sum

So this is a 2-part question (both parts I believe are closely related): How exactly does on express the sum $$\sum_{i=0}^{k}{i^n} = Q(n,k)$$ in a closed form For arbitrary positive integers ...
3
votes
2answers
90 views

Prove by induction that $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ is decreasing

I want to prove that the following sequence is monotonously decreasing: $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ I think it should be ...
2
votes
0answers
47 views

${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}$$ which can be proved combinatorically whether one particular element(among the $n$) is ...
1
vote
2answers
145 views

Finding a proof to the 'squares' problem

I am trying to find a proof for the general case of the solution to the 'Squares' Problem. This is what I have managed to figure out: If n is the number of squares in the top row, then the number ...
3
votes
1answer
36 views

Number of ways to color such that one color always leads

There are n boxes drawn out in a line. We have two colors, blue and red. We start coloring boxes from left to right. At any instant we want to color the boxes in such a way that number of boxes ...
1
vote
1answer
34 views

Binomial Coefficient Recusions

Let m and j be non-negative integers. Define $S^{0}_{m} = 1$ and: $ S^{j}_{m} = \displaystyle\sum\limits_{i=1}^{m} S_{i}^{j-1}$ Show via induction: $ S_{m}^{j} = {m+j-1 \choose j} $ I can ...
2
votes
3answers
132 views

Proof that $\binom{ n}{k} \in \mathbb N$

This problem is from Spivak. Give another proof that $\binom{n}{k}$ is a natural number by showing that $\binom{n}{k}$ is the number of sets of exactly $k$ integers each chosen from $1, \ldots,n$. I ...
1
vote
3answers
72 views

prove combinatorical identity using induction

Question: prove by induction on $n+m$ the combinatoric identity: $$\sum_{k = 0}^n {m + k \choose k} = {m + n + 1 \choose n}$$ I've tried to do on both $n$ and $m$ but I think it isn't the right way. ...
0
votes
2answers
37 views

Math Induction to prove recursion

This is a problem from a practice test. I don't understand how the answer was produced using math induction. And yes, math induction is required for this problem. Define a function f: $\mathbb{N}$ ...
0
votes
1answer
22 views

Proving by induction propositions of the type $P(n_1, n_2, …, n_k)$, where $n_1, n_2, …,$ and $n_k$ are natural numbers

For example: I've seen proofs of the multinomial theorem that use induction in the number of terms that are elevated at some power, but none that use induction in the exponent instead of using it in ...
0
votes
3answers
127 views

Strong Induction and Recursion

Consider the recursion given by \begin{equation}f(n) = 2f(n−1)− f(n−2)+6 \text{ for } n ≥ 2 \text{ with } f (0) = 2 \text{ and }f (1) = 4 \end{equation} Use mathematical induction to prove that ...
2
votes
2answers
105 views

show that $2n\choose n$ is divisible by 2 [duplicate]

I tried using induction, but in the inductive step, I get: If $2n\choose n$ is divisible then I want to see that $2n +2\choose n +1$ $${2n +2\choose n +1} = (2n + 2)!/(n+1)!(n +1)! = {2n\choose n} ...
5
votes
2answers
181 views

Number of bitstrings with $000$ as substring

I have $F_n$ number of bitstrings that have $000$, How would I prove that for $n \ge 4$ , $a_n = a_{n-1} +a_{n-2}+a_{n-3}+ 2^{n-3}$? Now there are many ways to go about this but if I choose starting ...
0
votes
0answers
110 views

Two very difficult induction proofs; having trouble with the inductive step

$$\sum_{k=0}^{n-2} \binom{n}{k}\binom{n}{k+1}\frac{n-2k-1}{k+1} = n-2 + \frac{1}{n+1}\binom{2n}{n}$$ $$\sum_{k=0}^{n-2} \binom{n}{k}\binom{n}{k+2}\frac{n-2k-1}{k+1} = -n + ...
1
vote
2answers
97 views

Recursive formula for tiling checkerboard

The question asks to find a recursive formula for $t(n)$ where $t(n)$ denotes the number of tilings a $2\times n$ checkerboard using only $1\times 1$ tiles and $L$-tiles (formed by removing the upper ...
4
votes
2answers
93 views

Counting tilings of a $2\times n$ board

Let $n=>1$ be an integer and consider a $2*n$ board $B_n$ consisting of $2n$ cells,each one having sides of length one. This picture shows $B_{13}$: For $n=>1$, let $a_n$ be the number of ...
2
votes
2answers
154 views

Proving strings [duplicate]

We consider strings of n characters, each character being a, b, c, or d, that contain an even number of as. (0 is even.) Let $E_n$ be the number of such strings.Prove that for any integer $n ...
1
vote
2answers
250 views

Show $\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$

My question is: show $$\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$$ $$n\geq m\geq 1$$ I tried to do this via induction and failed. there has to be another way of doing this. We could either ...
0
votes
1answer
23 views

An inequality related to Stirling Number of the second kind

I want to prove $C_{n,r}^2 \leq C_{n-1,r}C_{n+1,r}$ ($n \geq 2,r \geq 1$) where $C_{n,r}=\dfrac{\binom{n+r+1}{n}(n+r)!}{S_2(n+r,r)r!}$ and $S_2(n,k)$ is the Stirling number of the second kind, ...
1
vote
3answers
232 views

Sum of the area of all the rectangles in a rectangular

We have a rectangular shape with the size n × m meters is divided into rectangles of size 1 × 1 meters. Question: Sum of the area of all the rectangles that can be seen in that rectangular is how ...
5
votes
3answers
248 views

Given n $\in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

I tried to solve it using induction, but that got me no were, in the middle of the equation stat appearing ks that I don't see how to get out of the equation. I think the easiest way to prove it, it's ...
2
votes
0answers
95 views

Rearranging numbered cards to reverse their order

I have been thinking about this question for a long time, but I can't solve it. Here is the question: We have $9$ cards, with numbers one to nine written on them (in the order $1, 2, \ldots , 9$). ...
1
vote
1answer
326 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
3
votes
1answer
63 views

How to get the garage to work. (parking functions)

At McGeorge's garage every driver has a favourite parking spot. Parking spots are arranged in a line and are numbered 1 through n. A driver always goes to his favourite spot, if it's free he takes it. ...
4
votes
2answers
108 views

After Round Robin, there is always a player such that every other was either beaten by him or beaten by a player beaten by him

Every participant of a tournament plays with every other participant exactly once. No game is a draw. After the tournament, every player makes a list with the names of all the players, who either were ...
2
votes
3answers
173 views

Prove that $\sum^n_{k=1} k^2 = \binom{n+1}{2} + 2\binom{n+1}{3}$ for $n\geq 2$

Prove, for all $n\geq 2$ that $$\sum^n_{k=1} k^2 = \binom{n+1}{2} + 2\binom{n+1}{3}$$ Let us prove the inductive base for $n = 2$ $$\rm{LHS} = 1^2 + 2^2= 1 + 4 = 5$$ $$\rm{RHS} = \binom{3}{2} + ...
2
votes
2answers
66 views

Induction: $2^n = \sum_{v=0}^{n} \binom{n}{v}$ [duplicate]

I have to prove the following identity for $n \in \mathbb{N}$: $\displaystyle 2^n = \sum_{v=0}^{n} \binom{n}{v}$ Is there a way to show it through induction? Or is there a easier way? My steps so ...
2
votes
2answers
62 views

Proving combinatorical equality

I'm trying to prove the following inequality: $$ \sum_{k=0}^n {n \choose k}2^k=3n, \quad n\in \mathbb{N} $$ (The exercise says $n\geq 0$ but then the base case is incorrect so I'm assuming it's ...
4
votes
1answer
2k views

Exclusion Inclusion Principle Induction Proof

I got new home work that I was asked to proof the exclusion inclusion principle with induction, and my question is how can I do that? Any help will be appreciated!
1
vote
1answer
84 views

¿Mathematical induction GRE math?

Im studing for the GRE math subject test...i can´t get the followin problem: Using Mathematical Induction, show that it is possible to color with only two colors the regions formed by n lines in the ...
2
votes
2answers
147 views

Proving an identity by induction

Can you help me prove the following identity or refer to a proof for it: $$ \sum_{n=0}^{\infty}x^{n}\left(\begin{array}{c} n+1\\ i \end{array}\right)=\frac{x^{i-1}}{(1-x)^{i+1}}, $$ for ...
1
vote
1answer
60 views

Flavius Josephus: $J(2^i)=1~\forall i\geq 1$ (An Inductive Proof)

I'm asked to "[u]se induction to show that $J(2^i)=1$ for all $i\geq 1$. Where do I start? Here $J(n)$ is the last position of $n$ baskets with balls in them for which every second basket, starting ...
4
votes
3answers
253 views

An odd question about induction.

Given $n$ $0$'s and $n$ $1$'s distributed in any manner whatsoever around a circle, show, using induction on $n$, that it is possible to start at some number and proceed clockwise around the circle to ...
0
votes
2answers
67 views

Prove by induction: $\forall n\in\mathbb{Z}_{\geq1}:3\ |\ (6n^2-12n+3)$

I'm not sure how to start this induction problem. I was told that we start doing induction by using a base case $n=1$. Then we set $n=k$ to prove $n=k+1$. But how do I prove that ...
1
vote
3answers
113 views

Proving $\sum_{k=1}^nk^3 = \left(\sum_{k=1}^n k\right)^2$ using complete induction [duplicate]

I tried to prove the following statement using complete induction but I couldn't manage to solve it because I got a complex notation eventually. The statement is the following: $$\sum_{k=1}^nk^3 = ...
2
votes
0answers
77 views

Checking an inductive proof on a combinatorial product

Consider the following product, for $n, k, i \in \Bbb Z_+, k \geq 2$: $$ {\prod_{\ell = 1}^i {n + k - \ell \choose k } \over \prod_{\ell = 1}^{i-1} { k + \ell \choose k}} \tag{$*$} $$ It has been my ...
1
vote
2answers
109 views

Using mathematical induction to prove an identity related to combinatorics

Using Mathematical induction on $k$, prove that for any integer $k\geq 1$, $$(1-x)^{-k}=\sum_{n\geq 0}\binom{n+k-1}{k-1}x^n$$ How should I proceed? The tutorial teacher attempted this question and ...
1
vote
1answer
58 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
72 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
308 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
282 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
238 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 ...
1
vote
6answers
1k views

Prove by induction: For all N = 0, 1, 2, 3, ..: every finite set with N elements has exactly $ 2^N $ subsets. [duplicate]

For all N = 0, 1, 2, 3, ..: every finite set with N elements has exactly $ 2^N $ subsets. How do I prove this by induction?
3
votes
5answers
313 views

Proving the total number of subsets of S is equal to $2^n$

Student here! Just reading Liebecks Introduction to pure mathematics for fun and I made an attempt at proving the total number of subsets of S is equal to $2^n$. I realized that the total number of ...
1
vote
4answers
104 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
81 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 ...