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

learn more… | top users | synonyms

2
votes
3answers
463 views

Fibonacci Numbers Proof

Prove the following fibonacci sequence, which appear in Pascal's Triangle. I am not sure where to start on this, any pointers? $$ f_n = {n\choose0} + {n-1\choose1} + ... + {n-k\choose k}$$ where ...
1
vote
1answer
43 views

Permutations, Combinations, and Counting

A group of 63 people are camping together. They have two 6-person tents, three 4-person tents, five 3-person tents, and three 2 person tents. 18 people will sleep outside of the tents under a tarp. ...
2
votes
1answer
49 views

How many answers can be created using the elementary arithmetic operators?

If I gave you an amount of $n$ numbers, how many anwswer will you be able to create using the elementary arithmetic operators ($+, -, \times, /$)? These are the rules: All numbers ...
0
votes
2answers
30 views

Subsets and Cardinality

I'm confused on if I should count a subset as one element or if I should count all the elements of that subset when computing cardinality. Example: Given the set $A = \{1,2,3,\{4,5,6\}\}$ does $A$ ...
1
vote
1answer
29 views

Convert adjacency matrix to graph

Is there any online service that can provide possible graphs (the simplest one) when I give a sequence of integers (node degrees) as input (or reject the input) -based on Erdős-Gallai formula? Thanks ...
0
votes
1answer
47 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
0
votes
0answers
14 views

Solution of definite integral of product of bessel function and exponential

I have an integral $I=\int_{\theta} \int_r J_m(k_1r)e^{-j[P_x r \cos(\theta)+P_y r \sin(\theta)]} r dr d\theta$ $0\leq\theta\leq2\pi; r<\infty$ is there any method to solve this?
0
votes
1answer
19 views

Find a formula for the integer with smallest absolute value that is congruent to an integer $a \bmod m$, where $m$ is a positive integer.

Question: Find a formula for the integer with smallest absolute value that is congruent to an integer $a \bmod m$, where $m$ is a positive integer. My attempt: I don't completely understand the ...
0
votes
1answer
51 views

What is the derivation of A not being a proper subset of B?

The exact question is actually "Derivation A ⊄ B", and I am assuming that derivation in this case means to prove and give an example of when this is true? If it is then A is not a proper subset of B ...
0
votes
2answers
32 views

Use the Binomial Theorem to show that $0 = \sum_{k=0}^ n (-1)^{k} {n \choose k }$ [closed]

Use the Binomial Theorem to show that "$$0 = \sum_{k=0}^ n (-1)^{k} { n \choose k}$$".
0
votes
1answer
35 views

$a \equiv b(\bmod m) \iff a \bmod m = b \bmod m$

$a \equiv b(\bmod m) \iff a \bmod m = b \bmod m$ My attempt: $a \equiv (\bmod m) \Leftarrow a (\bmod m) = b (\bmod m)$ $\exists q_1, q_2\in\mathbb{R} | (a = m*q_1 + r) \wedge (b = m*q_2 + r)$ ...
1
vote
1answer
31 views

Discrete math and rules of inference

I recently did this rules of inference/logic question and the method I used was different from the textbook so I was wondering if my work was correct?
0
votes
1answer
40 views

How to derive this formula about the bracket function?

Is there a direct way of proving that $$ [nx] = [x] + [x+\frac{1}{2}] + [x+\frac{1}{3}] + \ldots + [x+ \frac{1}{n}]$$ for each real number $x$ and for each positive integer $n$? My effort: Let ...
4
votes
2answers
34 views

Proving Induction $(1\cdot2\cdot3)+(2\cdot3\cdot4)+…+k(k+1)(k+2)=k(k+1)(k+2)(k+3)/4$

I need a little help with the algebra portion of the proof by induction. Here's what I have: Basis Step: $P(1)=1(1+1)(1+2)=6=1(1+1)(1+2)(1+3)/4=6$ - Proven Induction Step: ...
2
votes
2answers
71 views

Solving the equation $n\log n = 10^9$

This seems very basic (I guess my calculus needs brushing up). Is there a way to find n without a calculator in this one? $10^{9} = n\log(n)$ My Attempt (log is base 2 base on the book convention.) ...
1
vote
1answer
63 views

The relationship between each harmonic numbers

In Knuth's "Concrete Mathematics" in chapter about numbers below equality is given $$H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{\epsilon_n}{120n^4} $$ where $0 < \epsilon_n < ...
1
vote
1answer
77 views

First Order Logic Consistency Big Problem

as i read some tutorial material on First Order Logic, i deduce that the following formula was consistent in FOL except the third one. am i right? i have doubt about the first one. any idea? thanks to ...
0
votes
2answers
68 views

Show that $\binom{n}{k}< \binom{n}{k+1}$ if and only if $k < (n-1)/2$ [closed]

Show that $\binom{n}{k} < \binom{n}{k+1}$ if and only if $k < \frac{n-1}{2}$ and then use this to deduce that the maximum of $\binom{n}{k}$ for $k=0,1,\dots,n$ is $\binom{n}{\lfloor ...
0
votes
0answers
12 views

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid?

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid? For a matroid, the codomain of the weight function is $[0,\infty)$, from Wikipedia ...
4
votes
1answer
67 views

Closed form of $\sum_{k=0}^nk\binom{k}{3}\binom{2n}{k}$

Recently, I came across the following exercise on the course of discrete math Find a closed form for $\sum_{k=0}^nk\binom{k}{3}\binom{2n}{k}$ So I tried some of the usual techniques: Let ...
1
vote
5answers
39 views

discrete mathematics and proofs

Let $a$ and $b$ be in the universe of all integers, so that $2a + 3b$ is a multiple of $17$. Prove that $17$ divides $9a + 5b$. In my textbook they do $17|(2a+3b) \implies 17|(-4)(2a+3b)$. They do ...
3
votes
1answer
31 views

how many ways can 1001 people win 500 identical items?

the question is stating that $1001$ people are in a race and there are $500$ objects that are identical (say the same shirts). We need to find the number of ways that the 500 shirts can be given out ...
2
votes
1answer
42 views

Proof Verification for Discrete Math Class

Prove that $n^2$ is even iff $n$ is even. I proved it like this: Case I: $n$ is even 1) $n = 2a$ $(a\in Z)$ 2) $n^2 = 4a^2 = 2(2a^2)$ 3) $2a^2 = K$ $(K \in Z)$ 4) $n^2 = 2K$ Case II: $n$ is ...
1
vote
1answer
43 views

Meaning of the characteristic polynomial of a matroid

From wikipedia The characteristic polynomial of a matroid $M$ (which is sometimes called the chromatic polynomial,[29] although it does not count colorings), is defined to be $$ p_M(\lambda) ...
1
vote
1answer
34 views

Mathematical induction of the harmonics number

My textbook has the steps to prove it, but I can't comprehend the steps that the textbook are showing. Can someone explain the math or logic used going from steps red to yellow and finally green?
9
votes
1answer
86 views

How many Sudoku puzzles are there with at least one solution?

A Sudoku puzzle is a 9 by 9 matrix of blanks(which we can represent as 0), and elements of the set {1,2,3,4,5,6,7,8,9}. How many Sudoku puzzles are there with at least one solution. Yes, I am even ...
0
votes
0answers
61 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
2
votes
2answers
41 views

What are a geometric system and a finite geometry?

Wikipedia says A finite geometry is any geometric system that has only a finite number of points. I wonder what a geometric system is? Is it some set system $(E, F)$, where $E$ is a set and $F ...
0
votes
2answers
68 views

prenex normal equivalence challenges in math

consider these two following formula are prenex normal equivalence with the above formula? i think yes, but didn't have any idea to explain it.
0
votes
1answer
42 views

Logic Pure Subset Problem

for example if we define : $$ \$(p,q,r) = (p\to q)\land(\neg p\to r)$$ how we can inference that set $\{\$,\top,\bot\}$ is Full Functional and not any pure subset of this be full functional.
1
vote
1answer
38 views

Initial value of Newton Raphson Method

I am currently studying Newton-Raphson Method. I feel that I understand the concept of it. Somehow, I am facing some question in my head about how to actually apply it. The questions that I have are ...
0
votes
3answers
43 views

How do I finish this summations problem?

I have posted a picture since I don't know how to make the summation symbols with the lower and upper summations on keyboard, sorry about that.. $$\sum_{a=1}^9\sum_{b=0}^9(101a+10b)$$ The answer is ...
0
votes
1answer
122 views

Logic challenge in math

i get stuck in logic problem. suppose $L=\{P,Q\}$ which $P$ and $Q$ are one-place predicate. if $A$ is a set with three element. how many way we can convert $A$ into a Structure for $L$ that ...
0
votes
1answer
38 views

How to test mathematically if a number contains the highest digit of its radix?

Is there a way to test mathematically if a number contains the highest digit of its radix, and if so how? For example, 101 in base 2 contains the digit 1, highest in base 2; but 101 in base 3 does ...
2
votes
6answers
243 views

Discrete math induction problem.

I am stuck at this step in the inductive process and I was wondering if someone can help me out from where I am stuck. Question: if $n$ is a positive integer, prove that, ...
0
votes
3answers
37 views

Giving an equivalence relation that corresponds to set partitions

My question is: Give equivalence relation that corresponds to the partitions A1 = {1,3,5} A2 = {2} A3 = {4,6} of the set A = {1,2,3,4,5,6} I don't know what the format of the relation should be, in ...
7
votes
5answers
171 views

Does $\{1,2,\ldots,3000\}$ contain a subset of $2000$ integers with no member twice another?

Does the set $X=\{1,2,\ldots,3000\}$ contain a subset $A$ of $2000$ integers in which no member of $A$ is twice another member of $A$? I started by putting $P=[1501,3000]$, but twice any integer in ...
0
votes
2answers
43 views

Factor n=59305397 given that $ p-q \le 10 $

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n} $ Rearranging the $p-q$ equation, I get $$ p+q = \sqrt{(p-q)^2 +4n}$$ So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$ However ...
2
votes
2answers
75 views

Combination small challenge problem

How many ways can 3 different Scientific Groups be formed using 5 students such that Each student is at least be a member of one committee and each two committee has exactly 2 students in common? I ...
0
votes
3answers
96 views

Proof for Concrete Mathematics 3.24

I'm reading Concrete Mathematics by Graham, Knuth, Patashnik . I found that for every integer $n$, this holds : $$n = \lceil n/m \rceil + \lceil (n-1)/m \rceil + \cdots + \lceil (n-m+1)/m \rceil$$ I ...
1
vote
1answer
28 views

Find how many People Like dancing Only,People Like Movies

A survey was conducted among 402 persons regarding their interest in movies,dancing and games it was found that (i) 100 People Like games. (ii) 142 People Like movies or dancing but not games. (iii) ...
0
votes
1answer
23 views

Define a numeric relation that is reflexive, but not symmetric or transitive.

Define a numeric relation that is reflexive, but not symmetric or transitive. I've googled on this one quite a bit and am stuck.
1
vote
1answer
26 views

chinese remainder theorem constructive proof

I am trying to understand CRT constructive proof from wikipedia [http://en.wikipedia.org/wiki/Chinese_remainder_theorem#A_constructive_algorithm_to_find_the_solution] I am unable to follow it from ...
1
vote
1answer
31 views

Probability of a certain result obtaioned by throwing an octahedron

Assume having a fair octahedron. We throw it $93$ times and get the following results: $\{33;7;8;1;2;0;5;37\}$ The numbers represent how many times the die fell on side $1, 2,...., 8$. What is the ...
0
votes
0answers
42 views

which of the following sets are nonempty?

Problem: $$\left\{x\,|\,x\in\mathbb{N},\,2x+7=3\right\}$$ Steps I took to solve it: $$\begin{array}{c} 2x + 7 = 3 \\ 2x = 3 - 7 \\ x = - 2 \end{array}$$ Hence, it is an empty set (not nonempty), but ...
-3
votes
0answers
49 views

Every polynomial of degree $\geq 1$ in $F[x]$ , $F$ a field, is irreducible or factors into a product of irreducible polynomials.

I am trying to prove the following: Every polynomial of degree $n\geq 1$ in $F[x]$, $F$ a field, is irreducible or factors into a product of irreducible polynomials. I don't understand fields ...
1
vote
2answers
40 views

Equality of two sets written differently

$$A = \{2m+ 1:m \text{ exists in } \mathbb{Z}\}$$ $$B= \{2n + 3:n \text{ exists in } \mathbb{Z}\}$$ For this question, it seems that $A=B$, and we know it's equal because we can just plug in numbers ...
0
votes
2answers
39 views

What is the difference between these empty set questions?

a) Ø ⊂ Ø False b) Ø ⊂ {Ø} True c)Ø ⊆ Ø True d)Ø ⊆ {Ø} True I am particularly confused with the difference of having {} and not having the braces because it seems that the braces make "b" true ...
0
votes
1answer
21 views

Check these recursive definitions for me?

Looking for Give a recursive definition of A) the set of odd positive integers B) the set of positive integer powers of 3 C) the set of polynomials with integer coefficients I have a. Basis: ...
3
votes
1answer
67 views

Determine Units of a Ring $\mathbb{Z}[\alpha]$

I am trying to determine the units of $Z[\alpha]$ where $\alpha$ satisfies the monic polynomial $\alpha^4+\alpha^3+\alpha^2+\alpha+1$. I found $Z[\alpha] := \lbrace a+b\alpha+c\alpha^2+d\alpha^3\;|\; ...