1
vote
1answer
25 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
82 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
42 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
140 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
32 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
127 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
67 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
35 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
103 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
98 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
177 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
81 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
92 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
153 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
201 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
228 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 ...
3
votes
3answers
185 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
93 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
237 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. ...
0
votes
0answers
35 views

use induction to prove that $Y_m$ = $X_{m-1}$ is true [duplicate]

use induction to prove that $Y_m$ = $X_{m-1}$ is true $X_0 = 1$ $X_1 = 1$ $X_m=\sum_{n=0}^{m-1} X_n X_{m-1-n} , m >1$ and $Y_1 = 1$ $Y_2 = 1$ $Y_m=\sum_{n=1}^{m-1} Y_n Y_{m-n} , m >1$ ...
2
votes
3answers
168 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
60 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
1k 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
79 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
134 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
58 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
251 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
66 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
108 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
71 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
99 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
299 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
272 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
224 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 ...
3
votes
5answers
264 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 ...
0
votes
4answers
100 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 ...
0
votes
3answers
227 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
198 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 ...
6
votes
2answers
2k 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
63 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 ...
1
vote
3answers
121 views

Induction proof of $\sum_{k=1}^{n} \binom n k = 2^n -1 $

Prove by induction: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$ for all $n\in \mathbb{N}$. Today I wrote calculus exam, I had this problem given. I have the feeling that I will get $0$ points for my ...