Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-mathematics]

The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

310
votes
24answers
33k views

Zero to the zero power – is $0^0=1$?

Could someone provide me with a good explanation of why $0^0=1$? My train of thought: $x>0$ $0^x=0^{x-0}=0^x/0^0$, so $0^0=0^x/0^x=\,?$ Possible answers: $0^0\cdot0^x=1\cdot0^0$, so $0^0=1$ $...
45
votes
13answers
8k views

Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$

After reading this question, the most popular answer use the identity $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$ What's the name of this identity? Is it the identity of the Pascal's triangle ...
115
votes
31answers
59k views

Sum of First $n$ Squares Equals $\frac{n(n+1)(2n+1)}{6}$

I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals: $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$ I really ...
7
votes
9answers
2k views

How to compute the formula $\sum \limits_{r=1}^d r \cdot 2^r$?

Given $$1\cdot 2^1 + 2\cdot 2^2 + 3\cdot 2^3 + 4\cdot 2^4 + \cdots + d \cdot 2^d = \sum_{r=1}^d r \cdot 2^r,$$ how can we infer to the following solution? $$2 (d-1) \cdot 2^d + 2. $$ Thank you
30
votes
5answers
3k views

Can $\sqrt{n} + \sqrt{m}$ be rational if neither $n,m$ are perfect squares?

Can the expression $\sqrt{n} + \sqrt{m}$ be rational if neither $n,m \in \mathbb{N}$ are perfect squares? It doesn't seem likely, the only way that could happen is if for example $\sqrt{m} = a-\sqrt{n}...
32
votes
6answers
18k views

Questions on “All Horse are the Same Color” Proof by Complete Induction

I'm bugged by the following that's summarized on p. 109 of this PDF. False theorem: All horses are the same color. Proof by induction: $\fbox{$P(n)$ is the statement: In every set of ...
19
votes
8answers
4k views

Showing that an equation holds true with a Fibonacci sequence: $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

Question: Let $F_n$ the sequence of Fibonacci numbers, given by $F_0 = 0, F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. Show for $n, m \in \mathbb{N}$: $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$ ...
127
votes
6answers
60k views

Using proof by contradiction vs proof of the contrapositive

What is the difference between a "proof by contradiction" and "proving the contrapositive"? Intuitive, it feels like doing the exact same thing. And when I compare an exercise, one person proves by ...
4
votes
6answers
2k views

Number of occurrences of k consecutive 1's in a binary string of length n (containing only 1's and 0's)

Say a sequence $\{X_1, X_2,\ldots ,X_n\}$ is given, where $X_p$ is either one or zero ($0 < p < n$). How can I determine the number of strings, which do contain at least one occurrence of ...
25
votes
6answers
9k views

Why is mathematical induction a valid proof technique? [duplicate]

Context: I'm studying for my discrete mathematics exam and I keep running into this question that I've failed to solve. The question is as follows. Problem: The main form for normal induction over ...
6
votes
4answers
4k views

Let $A$ be any uncountable set, and let $B$ be a countable subset of $A$. Prove that the cardinality of $A = A - B $

I am going over my professors answer to the following problem and to be honest I am quite confused :/ Help would be greatly appreciated! Let $A$ be any uncountable set, and let $B$ be a countable ...
4
votes
5answers
2k views

Sum with binomial coefficients: $\sum_{k=0}^{n}{2n\choose 2k}$

I'm repeating material for test and I came across the example that I can not do. How to calculate this sum: $\displaystyle\sum_{k=0}^{n}{2n\choose 2k}$?
7
votes
2answers
6k views

Counting number of moves on a grid

Imagine a two-dimensional grid consisting of 20 points along the x-axis and 10 points along the y-axis. Suppose the origin (0,0) is in the bottom-left corner and the point (20,10) is the top-right ...
15
votes
5answers
11k views

Proving prime $p$ divides $\binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$

Prove if $p$ is a prime then $p \mid \binom pk$ for $k\in\{1,\ldots,p-1\}$ I don't really know where to begin with this one. I can see that I have to use the fact that $p$ is prime somewhere - the ...
13
votes
2answers
8k views

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions if no two of these lines are parallel and no three pass through a common point. I know we start with the base case, where, ...
7
votes
5answers
2k views

$A \oplus B = A \oplus C$ imply $B = C$?

I don't quite yet understand how $\oplus$ (xor) works yet. I know that fundamentally in terms of truth tables it means only 1 value(p or q) can be true, but not both. But when it comes to solving ...
6
votes
6answers
6k views

General formula for the 1; 5; 19; 65; 211 sequence

I have got array $1; 5;19; 65; 211$. Can I find general formula for my array? For example, general formula for array $1; 2; 6; 24; 120$ is $n!$. I tried a lot for finding the general formula, but I ...
27
votes
4answers
91k views

How many distinct functions can be defined from set A to B?

In my discrete mathematics class our notes say that between set $A$ (having $6$ elements) and set $B$ (having $8$ elements), there are $8^6$ distinct functions that can be formed, in other words: $|b|^...
5
votes
3answers
2k views

Prove $f(S \cup T) = f(S) \cup f(T)$

$f(S \cup T) = f(S) \cup f(T)$ $f(S)$ encompasses all $x$ that is in $S$ $f(T)$ encompasses all $x$ that is in $T$ Thus the domain being the same, both the LHS and RHS map to the same $y$, since the ...
2
votes
3answers
335 views

How to get the correct angle of the ellipse after approximation

I need to get the correct angle of rotation of the ellipses. These ellipses are examples. I have a canonical coefficients of the equation of the five points. $$Ax ^ 2 + Bxy + Cy ^ 2 + Dx + Ey + F = 0$...
2
votes
5answers
8k views

Proving $ 1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$ for all $n\geq 2$ by induction

Question: Let $P(n)$ be the statement that $1+\dfrac{1}{4}+\dfrac{1}{9}+\cdots +\dfrac{1}{n^2} <2- \dfrac{1}{n}$. Prove by mathematical induction. Use $P(2)$ for base case. Attempt at solution: ...
4
votes
3answers
799 views

Mod of numbers with large exponents [duplicate]

I've read about Fermat's little theorem and generally how congruence works. But I can't figure out how to work out these two: $13^{100} \bmod 7$ $7^{100} \bmod 13$ I've also heard of this formula: $...
4
votes
4answers
15k views

Sum of cubes proof [duplicate]

Prove that for any natural number n the following equality holds: $$ (1+2+ \ldots + n)^2 = 1^3 + 2^3 + \ldots + n^3 $$ I think it has something to do with induction?
18
votes
2answers
24k views

What exactly is the difference between weak and strong induction?

I am having trouble seeing the difference between weak and strong induction. There are a few examples in which we can see the difference, such as reaching the $k^{th}$ rung of a ladder and proving ...
12
votes
5answers
4k views

Show that if $g \circ f$ is injective, then so is $f$.

The Problem: Let $X, Y, Z$ be sets and $f: X \to Y, g:Y \to Z$ be functions. (a) Show that if $g \circ f$ is injective, then so is $f$. (b) If $g \circ f$ is surjective, must $g$ be surjective? ...
7
votes
4answers
13k views

Prove by Mathematical Induction: $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$

Prove by Mathematical Induction . . . $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$ I tried solving it, but I got stuck near the end . . . a. Basis Step: $(1)(1!) = (1+1)!-1$ $1 = (...
2
votes
2answers
2k views

Coupon Collector Problem with Batched Selections

I am trying to solve a variation on the coupon collector's problem. In this scenario, someone is selecting coupons at random with replacement from n different possible coupons. However, the person is ...
12
votes
2answers
13k views

Prove that $\mathcal{P}(A)⊆ \mathcal{P}(B)$ if and only if $A⊆B$. [duplicate]

Here is my proof, I would appreciate it if someone could critique it for me: To prove this statement true, we must proof that the two conditional statements ("If $\mathcal{P}(A)⊆ \mathcal{P}(B)$, ...
37
votes
3answers
3k views

A stronger version of discrete “Liouville's theorem”

If a function $f : \mathbb Z\times \mathbb Z \rightarrow \mathbb{R}^{+} $ satisfies the following condition $$\forall x, y \in \mathbb{Z}, f(x,y) = \dfrac{f(x + 1, y)+f(x, y + 1) + f(x - 1, y) +f(x, ...
13
votes
6answers
25k views

Number of relations that are both symmetric and reflexive

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive? The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...
14
votes
3answers
5k 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 ...
3
votes
3answers
767 views

Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer

Letting $f_n$ be the Fibonacci numbers, show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer. Just some homework help. Need to prove. Thank you in ...
64
votes
8answers
14k 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 ...
18
votes
3answers
6k views

Gay Speed Dating Problem

Here's an interesting problem that I came up with the other night. With straight speed dating, (assuming the number of men and women are equal) the number of iterations that need to be made before ...
11
votes
2answers
93k views

Proof by induction: $2^n > n^2$ for all integer $n$ greater than $4$ [duplicate]

I am a CS undergrad and I'm studying for the finals in college and I saw this question in an exercise list: Prove, using mathematical induction, that $2^n > n^2$ for all integer n greater than $...
17
votes
2answers
1k views

Prove $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt{n}}}}<3$ by induction.

Problem: prove $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt{n}}}}<3$ by induction. I tried some, but stopped in $\sqrt[2^n]{n+1}$. Also tried with $2\sqrt{3\cdots}<3^2$ and so on.
1
vote
1answer
617 views

Element of, subset of and empty sets

I am trying to make sense of these. To me a is false because the set isn't empty. Is that correct? b is true because the empty set is an element of that set. c is false because the set the empty set ...
1
vote
2answers
1k views

Let $(a,b)$ and $(c,d)$ be intervals in $\Bbb R$, and find an injective and surjective function from $(a,b)$ to $(c,d)$

So here is this question I got stuck on: Let $(a,b)$, $(c,d)$ be intervals (not sure if that's the correct term) on $\Bbb R$, so that $a<b$, $c<d$. Find an injective and surjective function $f:(...
3
votes
5answers
10k views

Proving the summation formula using induction: $\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$

I am trying to prove the summation formula using induction: $$\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$$ So far I have... Base case: Let n=1 and test $\frac{1}{k(k+1)} = 1-\frac{1}{n+1}$ $...
78
votes
11answers
102k views

What is the best book for studying discrete mathematics?

As a programmer, mathematics is important basic knowledge to study some topics, especially Algorithms. Many websites, and my fellows suggest me to study Discrete Mathematics before going to Algorithms,...
29
votes
2answers
3k views

Combinatorial interpretation of Binomial Inversion

It is known that if $f_n = \sum\limits_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is ...
20
votes
8answers
48k views

prove that a connected graph with $n$ vertices has at least $n-1$ edges

Show that every connected graph with $n$ vertices has at least $n − 1$ edges. How can I prove this? Conceptually, I understand that the following graph has 3 vertices, and two edges: a-----b-----c ...
17
votes
4answers
35k views

How many distinct ways to climb stairs in 1 or 2 steps at a time?

I came across an interesting puzzle: You are climbing a stair case. It takes $n$ steps to reach to the top. Each time you can either climb $1$ or $2$ steps. In how many distinct ways can you ...
12
votes
4answers
9k views

Cardinality of a set A is strictly less than the cardinality of the power set of A

I am trying to prove the following statement but have trouble comprehending/going forward with some parts! Here is the statement: If $A$ is any set, then $|A|$ $<$ $|P(A)|$ Here is what I ...
5
votes
3answers
15k views

Using Euler's Totient Function, how do I find all values n such that $\phi(n)=12$?

How do I generalize the equation to be able to plug in any result for $\phi(n)=12$ and find any possible integer that works?
11
votes
2answers
11k views

Choosing numbers without consecutive numbers.

In how many ways can we choose $r$ numbers from $\{1,2,3,...,n\}$, In a way where we have no consecutive numbers in the set? (like $1,2$)
7
votes
6answers
433 views

Other Idea to show an inequality $\dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt n}\geq \sqrt n$

$$\dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt n}\geq \sqrt n$$ I want to prove this by Induction $$n=1 \checkmark\\ n=k \to \dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\...
6
votes
3answers
3k views

Creating a sequence that does not have an increasing or a decreasing sequence of length 3 from a set with 5 elements

Today my friend asked me following question: Consider the set $ A= \{1,2,3,4,5\}$ By using the elements of this set, can you find a permutation that neither has an increasing sequence of length 3, ...
12
votes
4answers
15k views

What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

This looks like a question asked earlier, but it isn't. $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{cases}$$ My professor gave this to me in ...
8
votes
2answers
1k views

Recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I have been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $$f(n)=5f\left(\frac n2\right)-6f\left(\frac n4\right) + n$$ Solve this recurrence relation ...