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.

learn more… | top users | synonyms

1
vote
0answers
37 views

How many pages of IRA (ASCII 7 bit) text with an average of 65 characters a line and 55 lines a page corresponds to one three-minute telephone call?

Explanation would be much appreciated. So far would I do know is that there are 180 seconds in 3 minutes. This question is part of my data communications class and I am seriously stuck.
-3
votes
1answer
44 views

Prove that (n + 1) (n choose m) = (n + 1 − m) ((n + 1) choose m) [closed]

Let m and n be integers with $0 ≤ m ≤ n$. There are $n + 1$ students in Carleton’s Computer Science program. The Carleton Computer Science Society has a Board of Directors, consisting of one president ...
0
votes
1answer
51 views

Prove (n choose k) ((n − k) choose (m − k)) = (n choose m) (m choose k)

Let k, m, and n be integers with 0 ≤ k ≤ m ≤ n, and let S be a set of size n. Prove that (n choose k) ((n − k) choose (m − k)) = (n choose m) (m choose k) by counting, in two different ways, the ...
0
votes
0answers
28 views

Conditional proof - Foundation of computer science

how can i prove !P using a conditional proof (not truth table) given P => Q ^ R and R => !Q so far i have, 1) P => Q^R premiss 2) R => !Q premiss 3) Q simplification 4) R simplification 5) !P v ...
0
votes
1answer
360 views

Suppose that A is a countable set. Show that the set B is also countable if there is an onto function f from A to B.

Is my logic correct/accepted? Let A be a countable set. Let f:A->B, surjective. $\exists$g:A->N, bijective. Using definition from 1. $\exists$h:N->B, surjective. $\therefore$B is countable by ...
1
vote
1answer
39 views

If $A⊂B$, can I assume that there exists an injective function $A\to B$?

Could I say that there exists a function $f\colon A\to B$, where $f(x)=x \in B$?
-1
votes
4answers
49 views

Solving Large Summations

So I'm aware that I can solve simple summations like: $\sum_{i=1}^{5} (2)/(i(i+2)$ By just pluging in i = 1 to 5 and summing up the values, but how would I go about approaching something like this? ...
2
votes
1answer
156 views

how many spanning trees do the graph have?

i) vertices = {1,2,3,4,5,6} edges = {12,23,34,45,46,62} 6edges, 6vertices 3 1 2 4 5 6 ii) vertices = ...
2
votes
2answers
32 views

Rewriting squareroot function in the form (a-b)(a+b)?

I have this function and I'm trying to write a program to compute it as n approaches 100. The problem is it overflows once it reaches around 50. The hint to solving this question is to rewrite the ...
0
votes
0answers
27 views

Reworked Induction Problem

The is a reworked problem from a previous post I corrected. Think I have it, but any pointers, corrections, criticisms are welcome. Thanks in advance. 1³+2³+···+n³ < ½n⁴ , ∀n∈ℕ, n≥3 For n=1, ...
3
votes
2answers
62 views

Prove the binomial coefficient equation [closed]

Prove the equation. I'm not sure where to begin $$ \sum_{k=0}^m \frac{{m \choose k}}{{n \choose k}} = \frac{n+1}{n+1-m} . $$
2
votes
6answers
383 views

Complex Permutation

How can we make $4$ letter words using $4$ letters (A,B,C,D) which satisfy following condition: The word cant starts or ends with A. A letter can be repeated more than once. Same letters can not ...
1
vote
1answer
69 views

recurrence relation of a language

I am looking at the following: Consider a language $X$ which consists of all bitstrings with no more than 2 consecutive zeros (represented by the above automaton). Next consider a sequence $s_n$ ...
1
vote
0answers
32 views

recursion trees and big theta bounds

Draw recursion trees and use them to find big theta bounds on the solutions to the following recurrences. For each, assume that T(1) = 1 and that n is a power of the appropriate integer. ex) T(n) = ...
0
votes
2answers
21 views

what would the cardinality be in the given set

Given $\{m \in \{0,1\}^b | m[2,3,4] = 100\}$ assuming that $b \geq 5$ and $b \in \mathbb{N}$ I'm thinking the cardinality of this set would be $2^b/3$ in terms of $b$ since there are $2$ choices ...
2
votes
4answers
327 views

Proof that $3^c + 7^c - 2$ by induction

I'm trying to prove the for every $c \in \mathbb{N}$, $3^c + 7^c - 2$ is a multiple of $8$. $\mathbb{N} = \{1,2,3,\ldots\}$ Base case: $c = 1$ $(3^1 + 7^1 - 2) = 8$ Base case is true. Now assume ...
1
vote
1answer
53 views

Proof rules in discrete math

When you write that a element is arbitrary, for example, "Let z be an arbitrary animal", does that automatically implies that you are using generalization rule as a proof?
0
votes
2answers
44 views

How to prove $\binom{n+1}{m+1}=\binom{0}{m}+\binom{1}{m}+\dots+\binom{n}{m}$ combinatorially

How can we prove combinatorially $$\binom{n+1}{m+1}=\binom{0}{m}+\binom{1}{m}+\dots+\binom{n}{m}$$ I can get LHS by asking: How many ways can we form an $m+1$ person committee from a group of $n+1$ ...
0
votes
1answer
30 views

Bijective proof of binomial determinant using gessel-viennot (from Aigner)

This is problem 5.74 (page 230) from Aigner "A Course in Enumeration". Give a bijective proof using Gessel-Viennot of $\text{det}$ ${m+i-1}\choose j$$^n_{i,j=1} =$${m+n-1}\choose n$ where ...
0
votes
1answer
57 views

Discrete Math and Well ordered sets

For my assignment they ask us the questions below. ...
3
votes
1answer
41 views

Prove/Disprove (alphabet, languages, subset)

I'm trying to prove or disprove the following, but am having some trouble. For all $Z \subseteq \Sigma^*$, $ZZ \subseteq Z$, where $\Sigma$ is some alphabet. For all $Z \subseteq \Sigma^*$, $Z ...
0
votes
0answers
23 views

Finding a lower bound to the van der waerden function W(r,k) using the Local lemma

Local lemma: https://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma So the title pretty much says it all. I'm considering each monochromatic arithmetic progression in the integers [1,...,n] to be the ...
0
votes
0answers
35 views

Induction of an Inequality

I have this induction problem I’ve been trying to solve. I can’t seem to close on it given my approach. Maybe my approach is all wrong, I’m not certain. Here is what I’ve done with it so far. ...
0
votes
1answer
30 views

first-order predicate calculus

We are given some functions, what they mean, and some statements and told to write the English sentence that describes the statement. I am having some trouble with this. Here is what we are given. ...
0
votes
1answer
54 views

Proof by Induction: "In a Zoo there are$\ k$ monkeys and$\ k$ monkey bars …

I'm struggling hard to prove the following statement/riddle by induction, it is given in the current assignement as a challenge. I really want to understand how to exactly approach such excersises. ...
1
vote
1answer
44 views

Incorrect proof

Consider the following Result: Let $n ∈ \mathbb{Z}$. Then $5n+7$ is even only if $n$ is odd. Next, consider the following proof. Assume first that $n$ is an odd integer. Then $n=2a+1$ for ...
0
votes
1answer
213 views

Climbing a n-stair staircase, taking 2 or 3 stairs each step…

Suppose a person has a n-stair staircase to climb, and they can go up exactly 2 or 3 stairs each time they take a step. Generate some initial data. Find and explain the recurrence relation to ...
1
vote
1answer
202 views

Tile a 1 x n walkway with 4 different types of tiles…

Suppose you are trying to tile a 1 x n walkway with 4 different types of tiles: a red 1 x 1 tile, a blue 1 x 1 tile, a white 1 x 1 tile, and a black 2 x 1 tile a. Set up and explain a recurrence ...
0
votes
1answer
64 views

Proof rules for quantifiers

Suppose my premise is "for all x: P(x)" and I am trying to prove "exists y: Q(y)". Which quantifier proof rule could I use in the first step of my proof, and which in the last? My answer to this ...
1
vote
1answer
29 views

Question about structural induction and predecessor relation

I have two questions, about structural induction and the predecessor relation. Why can't a relation be well-founded if it has an infinite descending chain, provided that it has a maximum element? How ...
3
votes
4answers
166 views

Let $S=\{3,4,5,6,7,8,9,10,11,12\}$. Suppose 6 integers are chosen from S. Must there be 2 integers whose sum is 15?

How can I go about solving this Pigeonhole Principle problem? So I think the possible numbers would be: $[3+12], [4+11], [5+10], [6+9], [7+8]$ I am trying to put this in words...
9
votes
3answers
798 views

How to prove indirectly that if $42^n - 1$ is prime then n is odd?

I'm struggling to prove the following statement: If $42^n - 1$ is prime, then $n$ must be odd. I'm trying to prove this indirectly, via the equivalent contrapositive statement, i.e. that if $n$ ...
1
vote
4answers
275 views

Equivalence relation

So I'm pretty new to abstract mathematics being a biologist an all. My biggest issue is that I can't really wrap my head around how to solve problems. So I have the problem: Let $X$ be the set of ...
0
votes
1answer
50 views

Cardinality in terms of $j$

I'm thinking of signing up to be a tutor and I'm reviewing material from a textbook to freshen up, but I've gotten stuck on this one. If we let $j \in \mathbb{N}$, how would we express the ...
0
votes
1answer
67 views

Express Statements with quantifiers

Let M(x, y) be the statement “x is a mother of y”, where the universe of discourse is the set of all people in the world. Express the statement "A person’s mother’s mother cannot be his/her mother." ...
2
votes
5answers
80 views

What is the coefficient of $x^3 y^4$ in the expansion of $ (2x-y+5)^8$

I was thinking of doing $\binom{8}{4}$ but not sure if right.
1
vote
0answers
69 views

Proving Quick Sort algorithm

Can we provide a proof for the correctness of the following quick sort algorithm: quicksort(a1,a2,...an) { (b) less := the empty list (c) greater := the empty list pivot = a1 for i := 2 to n if ...
1
vote
5answers
65 views

How can you prove $\binom {2n}{2} = 2\binom{n}{2} + n^2$? [closed]

Is there a way one can prove that this is true: ${2n \choose 2} = 2{n\choose 2} + n^2$ ? I am thinking it may involve binomial theorem.
16
votes
3answers
2k views

Counting numbers in a sequence - explain “Add $1$ before you're done” rule

I'm studying for the GRE, and my study book uses a rule that it never justifies for counting numbers in a sequence: "Add $1$ before you're done." For example, how many multiples of $3$ are between ...
-1
votes
1answer
28 views

Prove/Disprove: If a, b ∈ Z (with at least one not zero) and d = gcd(a, b) then d = gcd(a + b, a − b).

I believe this statement is true, but I've only tried one set of numbers (a = 8, b = 12). How would I go about proving this?
0
votes
2answers
295 views

In a group of 30 people, must at least 3 have been born in the same month? Why?

This is a pigeon hole principle problem and I'm not sure how I can word this to prove that at least 3 have been born in the same month out of 30 people?
0
votes
1answer
122 views

Rewriting statements without using any quantifiers

Let $ P$ and $Q$ be predicates on the set $S$, where $S$ has three elements, say, $S = {a, b, c}$. Then the statement $∀xP(x)$ can also be written in full detail as $P(a)∧P(b)∧P(c)$. Rewrite each of ...
3
votes
2answers
89 views

Prove $\sum_{i=1}^n i! \cdot i = (n+1)! - 1$?

Prove the summation: $$\sum_{i=1}^n i! \cdot i = (n+1)! - 1$$ using induction. base case: $n=1$: \begin{align*} \sum_{i=1}^1 i! \cdot i &= (1+1)! - 1 \\ 1 &= 2 - 1 \\ 1 &= 1 ...
1
vote
2answers
148 views

Prove that there must be two distinct integers in $A$ whose sum is $104$.

Let A be any set of $20$ distinct integers chosen from the arithmetic progression ${1,4,7,...,100}$. Prove that there must be two distinct integers in $A$ whose sum is $104$. Define ...
1
vote
2answers
45 views

Can a number be a subset of another set? [closed]

For example, if I had a set A = {2,4,6} is 2 ⊂ A true?
0
votes
1answer
32 views

Find the coefficient of the given term when (u^2 - v^2 ) ^10 expanded by the binomial theorem?

The term is u^16 v^4 When (u^2 - v^2 ) ^10 is exanded by the binomial theorem. My book uses Combinations, but I'm not sure if it works if u and v are squared?
0
votes
1answer
92 views

Basic Logic Gate Question

I have a question that states: "The output is 1 if and only if the input is 1" I have to identify what kind if gate this is. I believe it's an OR gate, because whenever you have a single 1 as input, ...
-3
votes
1answer
31 views

Writing sentence using propositional variables [closed]

How to write the sentence: "You can't ride with an elevator, if you are shorter than 150 cm, except you are older than 16 years old." using mathematics logic and propositional variables? For exemple ...
0
votes
2answers
30 views

Prove that given 4 elements from A, two of them must coincide in at least 2 places.

Let A be the set of all 8-digit numbers in base 3 (so they are written with the digits 0,1,2 only), including those with leading zeroes such as 00120010. Prove that given 4 elements from A, two ...
0
votes
2answers
349 views

Discrete Mathematics and Its Applications - Find $A^3$ if $A = \{a\}$ and if $A = \{0, a\}$

Find $A^3$ if $A = \{a\}$ and if $A = \{0, a\}$ I am doing some homework for my Discrete Mathematics class and I have run across this question that hasn't been discussed in my lectures, so I was ...