Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

7
votes
3answers
586 views

Decomposing a discrete signal into a sum of rectangle functions

Hello math@stackexchange community ! I have a simple question that seems to have a non trivial answer. Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar ...
6
votes
1answer
757 views

Relation between different ways of accessing bernoulli numbers with matrices

First Variant: Bernoulli numbers can easily be expressed by linear algebra equations. For example just using the recursion formula $$\sum_{k=0}^{n-1}{n\choose k}B_k=0$$ which is equation (34) from ...
5
votes
3answers
306 views

What does the notation $\binom{n}{i}$ mean?

What do the parentheses next to the summation involving the binomial coefficients mean? Like this: $$\sum _{i=0}^{n} \binom{n}{i}a^{(n-i)}b^i=\left(a+b\right)^n $$
4
votes
3answers
406 views

Stirling numbers of the second kind on Multiset

Stirling numbers of the second kind S(n, k) count the number of ways to partition a set of n elements into k nonempty subsets.What if there were duplicate elements in the set?That is,the set is a ...
3
votes
1answer
557 views

Adapted Towers of Hanoi from Concrete Mathematics - number of arrangements

I have a doubt concerning an exercise from Chapter 1 of "Concrete Mathematics". Actually, my doubt is in one exercise (exercise 3), but, since it depends on the previous exercise (2), I'm including it ...
2
votes
1answer
56 views

Exponentiation in terms of Summation

For positive integers, $a \times b=\sum\limits^{b}{a}$, correct? So therefore exponentiation where n is also a positive integer should be something like $a^n=\sum\limits^n{\sum\limits^a{a}}$ This is ...
2
votes
1answer
45 views

Stirling numbers with $k=n-2$

Is there a more general method of calculating: $$ \genfrac\{\}{0pt}{}{n}{n-2} $$ Like for :$$ \genfrac\{\}{0pt}{}{n}{n-1} $$ we can use $nC_2 $
2
votes
3answers
10k views

Is my understanding of antisymmetric and symmetric relations correct?

So I'm having a hard time grasping how a relation can be both antisymmetric and symmetric, or neither. Are my examples correct? symmetric & antisymmetric ...
1
vote
1answer
138 views

Where can I learn about solving Big-Oh problems that are written in algebra? [duplicate]

Where can I learn about solving Big-Oh problems that are written in algebra? Such as this $$\sum_{i=1}^{n} (3i + 2n) = O(n^2)$$
-1
votes
2answers
260 views

Showing that ${2n \choose 2} = 2 {n \choose 2} + n^2$ by combinatorial and algebraic arguments [closed]

Show that if $n$ is a positive integer, then ${2n \choose 2} = 2 {n \choose 2} + n^2$ a) using a combinatorial argument. b) by algebraic manipulation. How should I solve this problem ...
13
votes
9answers
1k views

What is the purpose of the first test in an inductive proof?

Learning about proof by induction, I take it that the first step is always something like "test if the proposition holds for $n = \textrm{[the minimum value]}$" Like this: Prove that ...
11
votes
3answers
424 views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$ I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
10
votes
2answers
972 views

Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?

I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$ $O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?
8
votes
1answer
356 views

Throwing balls into $b$ buckets: when does some bucket overflow size $s$?

Suppose you throw balls one-by-one into $b$ buckets, uniformly at random. At what time does the size of some (any) bucket exceed size $s$? That is, consider the following random process. At each of ...
8
votes
1answer
1k views

Number of ways to put $n$ unlabeled balls in $k$ bins with a max of $m$ balls in each bin

The number of ways to put $n$ unlabeled balls in $k$ distinct bins is $$\binom{n+k-1}{k-1} .$$ Which makes sense to me, but what I can't figure out is how to modify this formula if each bucket has a ...
7
votes
2answers
404 views

Visualizing Concepts in Mathematical Logic

If you were forced to speculate or offer anecdotal evidence, how would you say excellent practicioners of mathematical logic coneptually grasp statements like: $$ \vdash ((P \rightarrow Q) ...
6
votes
3answers
957 views

Shortest solution to order 26 alphabet letters, no two vowels occurring consecutively

What is the shortest solution to the following problem? What is the number of ways to order the 26 letters of alphabet so that no two of the vowels a,e,i,o,u occur consecutively? What I ...
6
votes
3answers
2k views

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number I've looked at http://math.stackexchange.com/a/19998 It is known that $2^n-1$ can only be prime if $n$ is ...
6
votes
1answer
311 views

Recurrence relation satisfied by $\lfloor(1+\sqrt{5})^n\rfloor$

Let $L(n)=\lfloor(1+\sqrt{5})^n\rfloor$. What kind of a linear recurrence is satisfied by $L(n)$? I have no idea how to go about this, because of the presence of the greatest integer function. ...
5
votes
1answer
111 views

Number of combinations such that each pair of combinations has at most x elements in common?

I am doing research on the sense of smell and have a combinatorics problem: I have 128 different odors (n) and I mix them in mixtures of 10 (r). There are 2.26846154e+14 different mixtures. What I ...
5
votes
2answers
1k views

Number of walks on 2D grid

Suppose we are on a finite 2D grid of points from $(0,0)$ to $(a,b)$. Each turn we can move up/down/left/right on this grid (we have 3 possible moves on edges and 2 on corners). In the beginning we ...
4
votes
3answers
160 views

$\Delta^d m^n =d! \sum_{k} \left[ m \atop k \right] { {k+n} \brace m + d}(-1)^{m+k}$ Is this a new formula?

(EDIT: The variable $z$ is changed to $d$ so as not to be confused with generating function notation) I have derived this formula involving the Stirling numbers that I now feel confident is correct ...
4
votes
1answer
118 views

An intuitive solution to this problem (Using probability tree)

A group of boys has been lost several days in the dessert. This group has a phone to make phone calls. After a long way walk, they believe that the current area is suitable for phone calls; even ...
4
votes
3answers
322 views

Help with combinatorial proof of binomial identity: $\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1}$

Consider the following identity: \begin{equation} \sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1} \end{equation} Consider the set $S$ of size $2n-2$. We partition $S$ into two sets $A$ ...
4
votes
4answers
1k views

Proving an equivalence relation on $\mathbb{Z}\times\mathbb{Z}$

I'm working on some discrete mathematics problems, and have run into an issue involving proving an equivalence relation. The relation I'm tasked with proving is the relation $R$ defined on ...
4
votes
6answers
2k views

Evaluate and prove by induction: $\sum k{n\choose k},\sum \frac{1}{k(k+1)}$

$\displaystyle 0\cdot \binom{n}{0} + 1\cdot \binom{n}{1} + 2\binom{n}{2}+\cdots+(n-1)\cdot \binom{n}{n-1}+n\cdot \binom{n}{n}$ $\displaystyle\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3}+\frac{1}{3\cdot ...
3
votes
1answer
70 views

Is there some way to simplify $\sum_{i=1}^n \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) $ To obtain a closed form.

Is there some way to simplify $\sum_{i=1}^n \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) $? Does it have a closed form? It's the last piece of a puzzle I need to solve a similar question ...
3
votes
1answer
85 views

Proof sought for a sum involving binomials that simplifies to 1/2

A proof of: $$\begin{align*}(1/2)^{2m+1} \sum_{k=0}^{m} \binom{m}{k} \sum_{j=0}^{k} \binom{m+1}{j} = \frac{1}{2} \end{align*} $$ Conjecture based on the following Maple code: ...
3
votes
3answers
360 views

Fractions in Ancient Egypt

In ancient Egypt, fractions were written as sums of fractions with numerator 1. For instance,$ \frac{3}{5}=\frac{1}{2}+\frac{1}{10}$. Consider the following algorithm for writing a fraction ...
3
votes
2answers
200 views

proving a sum of binomial coefficients

How can i prove that $\displaystyle\sum_{k=0}^{n}{2n\choose 2k}=2^{2n-1}$ I tried using induction and pascal's identity but it didn't help me.
3
votes
2answers
94 views

Pigeonhole principle and a decagon

This is a homework Question and has to do with Pigeonhole principle. Could use a hint. Q. The numbers ${0,1,2,.....9}$ are randomly assigned to the vertices ${x_0,x_1,...x_9}$ of a decagon. Show that ...
3
votes
1answer
157 views

Solving a recurrence relation, $a_n = \sqrt{n(n+1)}a_{n-1} + n!(n+1)^{3/2}$

I'm trying to solve the following recurrence relation, but I have a problem with the factorial part. I would like to evaluate its particular solution. I would like also to suggest a textbook for ...
3
votes
4answers
1k views

Number of straight line segments determined by $n$ points in the plane is $\frac{n^2 - n}{2}$

How can we prove by mathematical induction that for all $n$, the number of straight line segments determined by $n$ points in the plane, no three of which lie on the same straight line, is $\frac{n^2 ...
3
votes
1answer
68 views

A closed form for $T_N = 1 + \sum\limits_{k=0}^{N-2}{(N-1-k)T_k}$?

I've narrowed down a problem I am working on to the following recurrence: $$\begin{align*} T_0 &= T_1 = 1\\ T_N &= 1 + \sum_{k=0}^{N-2}{(N-1-k)T_k} \end{align*}$$ I'm stuck on how to close ...
2
votes
1answer
36 views

Matrix linear algebra generators

Linear algebra and special-linear group experts please help: It is known that in principle one can generate this $C$ matrix form the $A$ and $B$ matrix below. Here $$ C=\begin{pmatrix} 0& -1& ...
2
votes
2answers
56 views

Learning Mathematics through Programming.

I am about to embark on a 'comprehensive' and thorough study of undergraduate mathematics. In the interests of efficiency and a desire to improve my programming skills, I ask: In oppose to the pen ...
2
votes
8answers
200 views

Proving for every odd number $x$, $x^2$ is always congruent to $1$ or $9$ modulo $24$

A problem I have been presented with asks the following: Prove for every odd number $x$, $ x^2$ is always congruent to $1$ or $9$ modulo $24$. This seems odd and non-intuitive to me. Of course, it ...
2
votes
1answer
89 views

$n$ persons who make telephone calls

Lets say we have $n$ persons and everybody knows one specific thing which the other persons do not know. When two of the $n$ persons telephone they share their knowledge about the specific thing. How ...
2
votes
3answers
105 views

Cardinality: $\left|\Bbb N^{\Bbb N}\right| = \left|\{0,1\}^{\Bbb N}\right|$

Let $F$ be the set of functions from $\Bbb N$ to $\Bbb N$ and $G$ be the set of functions from $\Bbb N$ to $\{0,1\}$. Prove that $|F| = |G|$. What I tried doing is saying that every number in ...
2
votes
1answer
58 views

Finding a generating function of a series

So say if you have a sequence defined as, for $a\in\mathbb{Z}$, $$ c_n = \binom{a}{0} \binom{a}{n} - \binom{a}{1} \binom{a}{n-1} + \cdots+ (-1)^n \binom{a}{n} \binom{a}{0} = \sum_{i=0}^n (-1)^i ...
2
votes
3answers
141 views

Coloring dots in a circle with no two consecutive dots being the same color

I ran into this question, it is not homework. :) I have a simple circle with $n$ dots, $n\geqslant 3$. the dots are numbered from $1\ldots n$. Each dot needs to be coloured red, blue or green. No ...
2
votes
3answers
8k views

Largest prime factor of 600851475143 [duplicate]

I'm trying to use a program to find the largest prime factor of 600851475143. This is for Project Euler here: http://projecteuler.net/problem=3 I first attempted this with the code that goes through ...
2
votes
0answers
146 views

Can this series be expressed in closed form, and if so, what is it?

Can this series be expressed in closed form, and if so, what is it? $$ \sum_{n=1}^\infty\frac{1}{9^{n+1}-1} $$
2
votes
4answers
1k views

The asymptotic behaviour of $\sum_{k=1}^{n} k \log k$.

Trying to simplify the following expressions in $n$ to find its order of growth. I want to show the simplification separately from the order of growth $$\sum_{k=1}^{n} k \log k = \Theta(n^2 \log n)$$ ...
2
votes
3answers
513 views

Monty Hall Three-Door Puzzle

I have a doubt concerning a question about the Monty Hall Three-Door Puzzle, in probability. I found this problem in Rosen's "Discrete Mathematics and Its Applications". The Monty Hall Three-Door ...
1
vote
1answer
39 views

Applying the Chinese remainder theorem

I am trying to apply the Chinese remainder theorem to obtain the unique solution modulo $10^n$ for $N\equiv 1 \pmod {2^n}$ and $N\equiv 0 \pmod {5^n}$. I have reason to suppose that the solution is ...
1
vote
0answers
34 views

statistical distance identity

How do I show the following? Let $\vec{\rho}_X$,$\vec{\rho}_Y$ denote the probability distributions over a finite set $R$ respectively, and consider a function $f: R\to[0,1]$. Prove that ...
1
vote
1answer
36 views

proving identity for statistical distance

How do I show the following identity? Let $\vec{\rho}_X$,$\vec{\rho}_Y$ denote the probability distributions over a finite set $R$ respectively. Prove that ...
1
vote
4answers
86 views

Prove that $C_n < 4n^2$ for all n greater than or equal to 1

$C_1 = 0$, $C_n = C_{\lfloor n/2\rfloor} + n^2$ for all $n \ge 1$ Prove that $C_n < 4n^2$ for all $n \ge 1$. I don't know how to even approach this. I remember something about inductive ...
1
vote
0answers
88 views

Why these two problems lead to same answers?

Suppose these two problems: Problem 1: $$\min_{X,P} \quad\max_{1\leq l\leq L-1} \quad {|\sum_{1\leq i\leq N_p}^{N_p}x_ie^{\frac{2\pi l}{N}p_i}| \over {\sum_{i=1}^{N_p} x_i^2}} \quad \equiv \quad ...