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

learn more… | top users | synonyms

0
votes
2answers
117 views

Formal definition of Mathematical Induction & Strong Induction

I have been reading some notes on Induction and Strong Induction and fully understand how they work. However I was interested in a formal/mathematical way of expressing their definition and was ...
0
votes
3answers
59 views

Induction to prove $2n + 3 < 2^n$

I am having trouble and was wondering if someone could go over the steps slowly to show that: $$2n + 3 < 2^n \ \text{for} \ n \geq 4$$ Any help would be amazing!
0
votes
2answers
528 views

Find out all solutions of the congruence $x^2 \equiv29 \mod 5$.

Find out all solutions of the congruence $x^2 \equiv29 \mod 5$. [Hint:Find the solutions of this congruence $\mod 5$ , $\mod 7$ , and $\mod 7$ , and then use the Chinese Remainder Theorem.]
0
votes
1answer
185 views

Equivalence Relation? Column-equivalence on the set of all $m\times n$ matrices.

How do I show that column equivalence on the set of all $m\times n$ matrices is an equivalence relation? I know that to show it is an equivalence relation, I need to show that column equivalence is ...
0
votes
3answers
1k views

Isomorphism between two particular graphs

Are these two graphs isomorphic?
0
votes
1answer
69 views

How many cases are there in this specific example?

$\lfloor (n+m)/2\rfloor\ = \lfloor m/2\rfloor\ + \lceil n/2 \rceil $ I thought it was 4, but I am not sure n greater than 1 and greater than 2 m greater than 1 and greater than 2 trying to do a ...
0
votes
3answers
177 views

Is this a valid proof of $f(S \cap T) \subseteq f(S) \cap f(T)$?

$f(S \cap T) \subseteq f(S) \cap f(T)$ Suppose there is a $x$ that is in $S$, but not in $T$, then there is a value $y$ such that $f(x) = x$, that is in $f(S)$, but not in $f(S \cap T)$. Suppose ...
0
votes
3answers
983 views

Sum of three squares: need to check the expressions with the lower powers of $4$.

It is a well-known theorem that a positive integer cannot be expressed as a sum of three squares iff. it is of the form $4^n(8m+7)$ for some non-negative integers $m$ and $n$. E.g. ...
0
votes
1answer
1k views

Positive integers less than 1000 without repeated digits

How many integers from 1-999 do not have any repeated digits? The answer is explained in this link, but why is the last set 9*9*8? Why not 9*9*9?
0
votes
3answers
404 views

Discrete Fibonacci sequence problem

The Fibonacci sequence satisfies $F_0 = F_1 = 1$ and the recurrence relation $F_k=F_{k-1}+F_{k-2}$ for all integers $k\geq 2$. Prove that $F_k+2F_k-F_{2k+1}= (-1)^k$ for all integers $k\geq 0$.
-1
votes
1answer
325 views

how to determine the largest n for which one can solve within one second using an algorithm

So I am confused on this problem for my discrete math class, I didn't know if there was a specific formula you were supposed to use or what. The question is "What is the largest n for which one can ...
-2
votes
2answers
107 views

$x_1+x_2+\cdots+x_n\leq M$: Cardinality of Solution Set is $C(M+n, n)$

Show that the number of solutions in nonnegative integers of the inequality $$x_1+x_2+\cdots+x_n\leq M,$$ where $M$ is a nonnegative integer, is $C(M+n, n)$.
48
votes
19answers
11k views

Coin flipping probability game ; 7 flips vs 8 flips

Your friend flips a coin 7 times and you flip a coin 8 times; the person who got the most tails wins. If you get an equal amount, your friend wins. There is a 50% chance of you winning the game and a ...
53
votes
15answers
7k views

Prove if $n^2$ is even, then $n$ is even.

I am just learning maths, and would like someone to verify my proof. Suppose $n$ is an integer, and that $n^2$ is even. If we add $n$ to $n^2$, we have $n^2 + n = n(n+1)$, and it follows that ...
33
votes
5answers
992 views

How much weight is on each person in a human pyramid?

After participating in a human pyramid and learning that it's very uncomfortable to have a lot of weight on your back, I figured I'd try to write out a recurrence relation for the total amount of ...
18
votes
2answers
871 views

Is there a discrete version of de l'Hôpital's rule?

When considering asymptotics of runtime functions, you often have to find limits of quotients of discrete functions, e.g. $\displaystyle\qquad \lim\limits_{n \to \infty} ...
11
votes
3answers
3k views

Lights out game on hexagonal grid

I greatly enjoyed the Lights Out game described here (I am sorry I had to link to an older page because some wikidiot keeps deleting most of the page). Its mathematical analysis is here (it's just ...
15
votes
4answers
604 views

Decreasing integers on the blackboard

There are $n\geq 2$ copies of an integer $k>0$ written on the blackboard. A move consists of choosing an integer $m>0$ on the blackboard, and replacing it as well as one other integer on the ...
10
votes
7answers
11k views

Are there any good Discrete Mathematics video online?

I want to learn discrete mathematics by reading book by myself but I find sometime it's very hard to understand what author trying to say. I want to know, are there any good online video that teach ...
26
votes
8answers
2k views

What is $\gcd(0,0)$?

What is the greatest common divisor of $0$ and $0$? On the one hand, Wolfram Alpha says that it is $0$; on the other hand, it also claims that $100$ divides $0$, so $100$ should be a greater common ...
12
votes
3answers
689 views

Twenty questions against a liar

Here's one that popped into my mind when I was thinking about binary search. I'm thinking of an integer between 1 and n. You have to guess my number. You win as soon as you guess the correct number. ...
17
votes
3answers
507 views

A (probably trivial) Induction Problem: $\sum_2^nk^{-2}\lt1$

So I'm a bit stuck on the following problem I'm attempting. Essentially, I'm required to prove that $\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 1$ for all $n$. I've been toiling with some ...
5
votes
2answers
2k views

Maximization with xor operator

Few days ago i found task : with given N numbers only one of those numbers doesn't have pair, which one is it? After hours of surfing the net i found that XOR operator is good for that, because ...
14
votes
4answers
303 views

Solve recursion $a_{n}=ba_{n-1}+cd^{n-1}$

Let $b,c,d\in\mathbb{R}$ be constants with $b\neq d$. Let $$\begin{eqnarray} a_{n} &=& ba_{n-1}+cd^{n-1} \end{eqnarray}$$ be a sequence for $n \geq 1$ with $a_{0}=0$. I want to find a closed ...
7
votes
2answers
136 views

Every 33-length subsequence of $1,2,\dotsc,122$ contains a three term arithmetic progression

Is it possible to prove that every 33-length subsequence of the sequence $1,2,3,\dotsc,122$ contains a three term arithmetic progression? Maybe I should post it on mathoverflow
5
votes
2answers
92 views

Does $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs?

Q: Does the complete bipartite graph $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs, where $I$ is a $1$-factor (i.e., a perfect matching)? The obvious necessary conditions work: $K_{12,12}$ ...
4
votes
2answers
210 views

Combinatorics Pigeonhole problem

Hello to all! So i have to do this problem: In the course of an year of 365 days Peter solves combinatorics problems. Each day he solves at least 1 problem, but no more than 500 for the year. Prove ...
4
votes
4answers
254 views

Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$

How can I calculate the following sum involving binomial terms: $$\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$$ Where the value of n can get very big (thus calculating the binomial ...
4
votes
0answers
7k views

Relationship Between The Z-Transform And The Laplace Transform

Below I've quoted Wikipedia's entry that relates the Z-Transform to the Laplace Transform. The part I don't understand is $z \ \stackrel{\mathrm{def}}{=}\ e^{s T}$; I thought $z$ was actually an ...
3
votes
1answer
154 views

Catalan Numbers Staircase bijection

I need to give a bijective proof for the following problem (via R. Stanley Catalan Addendum). ($k^8$) tilings of the staircase shape $(n, n − 1, \dots , 1)$ with $n$ rectangles. For example, when $n ...
3
votes
3answers
182 views

Terminology re: continuity of discrete $a\sin(t)$

This question is specifically about the terminology used to explain a particular problem and its solution, not the math itself. I am a programmer, I am not really a math person, but I have at least an ...
3
votes
3answers
11k 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 ...
3
votes
3answers
137 views

“Fat” sets of integers and Fibonacci numbers

Let us call a set of integers "fat" if each of its elements is at least as large as its cardinality. For example, the set $\{10,4,5\}$ is fat, $\{1,562,13,2\}$ is not. Define $f(n)$ to count the ...
2
votes
3answers
190 views

Wheel of Fortune Problem

The Summation formula is $$\sum_{i=1}^ni =\frac{n(n+1)}2$$ How is it that we know the integers $1,2,...36$ appear exactly $3$ times. And why do we multiply the sum by $3$ in the last part of the ...
2
votes
0answers
37 views

an “alternate derivation” of Poisson summation formula and discrete Fourier transformation

Inspired by this post, I am trying to do a derivation of a Poisson summation formula. My starting point is this: $$ \frac{1}{2\pi} \int^{\infty}_{-\infty} e^{i k x} dx=\delta(k) $$ I simply wish ...
11
votes
7answers
2k views

What is the proof that the total number of subsets of a set is $2^n$?

What is the proof that given a set of $n$ elements there are $2^n$ possible subsets (including the empty-set and the original set).
9
votes
7answers
926 views

If $xy$ and $x+y$ are both even integers (with $x,y$ integers), then $x$ and $y$ are both even integers

The title statement can be proven using the contrapositive, note that $x$ odd or $y$ odd means that at least one of $x\cdot y,x+y$ is odd. Is there a way to prove the statement directly? To ...
8
votes
4answers
1k views

Coin problem with 6 and 10

I am doing a coin problem where: In a city where you only have denominations in 6 and 10. What is the largest value that this city cannot pay? In another problem that my teacher showed me, where ...
8
votes
2answers
2k views

Minimum degree of a graph and existence of perfect matching

I was reading a result where the following proposition appears as a preliminary step (and left as exercise): Claim: Suppose $G$ is a graph on $n$ vertices ($n$ even and $n \geqslant 3$) with ...
7
votes
3answers
217 views

Changing Summation Index Question

I'm sorry if this seems like a very novice question, but I am still relatively new to the world of discrete math ( still in 9th grade). I've been reviewing some of the concepts I learned in a ...
7
votes
3answers
625 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
797 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
336 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
1answer
66 views

What is the history of this theorem about the finite sum of a polynomial?

I discovered and proved the following theorem back in high school, and have waited patiently to hear something about throughout my college career (which is nearing it's end, hope to have finished my ...
4
votes
3answers
229 views

Number of binary strings with $n$ ones and $m$ zeros

$f(n,m)$ is the number of binary strings with up to $n$ ones and up to $m$ zeros. Prove that the number of possible strings is: $${n+m+2 \choose n+1} -1$$ I got to the point that: $$\sum_{a=0}^n ...
4
votes
3answers
1k views

Using generating functions find the sum $1^3 + 2^3 + 3^3 +\dotsb+ n^3$

I am quite new to generating functions concept and I am really finding it difficult to know how to approach problems like this. I need to find the sum of $1^3 + 2^3 + 3^3 +\dotsb+ n^3$ using ...
4
votes
1answer
642 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 ...
4
votes
1answer
2k views

Number of ways of choosing $m$ objects with replacement from $n$ objects

There is a set of $n$ distinct objects. How many possible multisets can we get when choosing $m$ objects with replacement? Note that the elements in a set are unordered and distinct, and the elements ...
4
votes
3answers
423 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 ...
2
votes
1answer
63 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 ...