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
2answers
94 views

Generating Functions for collection of balls

There are 10000 identical red balls, 10000 identical yellow balls and 10000 identical green balls. In how many different ways can we select 2005 balls so that the number of red balls is even or the ...
1
vote
2answers
84 views

What is the difference between a simple graph and a complete graph?

I might be having a brain fart here but from these two definitions, I actually can't tell the difference between a complete graph and a simple graph.
1
vote
4answers
42 views

Find $m$ and $n$

Two finite sets have m and n elements. Thew total number of subsets of the first set is 56 more than the two total number of subsets of the second set. Find the value of $m$ and $n$. The equation ...
0
votes
2answers
50 views

finding a boolean function with specific property

The problem I am trying to solve is: Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$. My solution is $$\left(p\wedge\thicksim ...
0
votes
1answer
47 views

What is the statement |x+y|≤|x|+|y| saying

|x+y|≤|x|+|y| I know that |x| means the cardinality of x for example. But it looks to me like its saying the cardinality of x plus y is less then or equal to the ...
0
votes
1answer
20 views

Proving Boolean Function

Can anyone help me if I am right....!! The Question Reads: Prove that not every boolean function is equal to a boolean function constructed by only using ^ and v. This is my answer by the double ...
-1
votes
1answer
56 views

list all the equivalence relation [duplicate]

list all the equivanlance relations in the set A={1,2,3,4) so there should be 15 right? so what I got so far (1 1) (22) (33) (44) (12) (13) (14) (21) (23) (24) (31) (32) (34) (41) (42) (43) these ...
1
vote
3answers
119 views

Which discrete mathematics book to read for a software engineer?

I'm a computer science student, but I lack a good mathematics background. So I decided to start working on that. I was searching in the topic and I found that for computer science a good knowledge of ...
0
votes
5answers
99 views

Find the solution to the recurrence relation: $a_n=3a_{n-1}+1; a_0=1$

$$a_n=3a_{n-1}+1; a_0=1$$ The book has the answer as: $$\frac{3^{n+1}-1}{2}$$ However, I have the answer as: $$\frac{3^{n}-1}{2}$$ Based on: Which one is correct? Using backwards substitution ...
0
votes
3answers
38 views

Need to check if this function is bijective

I don't understand how $f : \mathbb N \to\mathbb N$ (where $0$ isn't included in the natural numbers set), $f(n) = n^2$ is not bijective. It seems both injective and surjective to me? Thanks got it!
0
votes
1answer
34 views

Is a relation induced by a partition always an equivalence relation?

Is a relation induced by a partition always an equivalence relation? I'm having some serious trouble understanding this concept and I was wondering if this is true.
2
votes
1answer
71 views

Find the generating function for a series , given a recurrence relation

I am solving a problem on an Online Judge. The problems solution boils down to find the solutions to the following recurrence relation: ...
1
vote
1answer
36 views

Proving a relation is a total order relation

Consider question #21 part a: Here is the solution: However, consider the definition of a total order relation: The solution didn't prove that the relation is a partial order relation. This ...
4
votes
0answers
40 views

Subsets of cyclic group with distinct pairwise differences

Given a number $m\in\mathbb N$, let $\mathbb Z_m=\{0,1,\dots,m-1\}$ denote the ring of integers modulo $m$ (although we won't need multiplication, so any cyclic group of order $m$ will do). Given a ...
-1
votes
1answer
36 views

Which is a linear and homogeneous recurrence?

Which of the following choices is a linear and homogenous recurrence? $1)$ $A_n = A_{n-1} + 4A_{n-2} + 3n$ $2)$ $A_n = n + 1$ $3)$ $A_n = (A_{n-1})^2$ $4)$ $A_n = 5A_{n-1} + A_{n-2} + 3A_{n-3}$
-2
votes
2answers
145 views

Using generation functions solve the following difference equation

Using generation functions solve the following difference equation $$ a_{n+1} - 3a_{n+2} + 2a_n = 7n ; n\geq0; a_0 = -1; a_1 = 3. $$
0
votes
1answer
29 views

How to count the number of distinct equivalence classes for a relation involving truth tables?

I am having trouble with question 22 part (2): Here is the solution: How did the author know that there are 256 distinct equivalence classes? Where did they get $2^8$ from?
2
votes
1answer
171 views

Is my conjecture correct? Any advice on how to solve this conjecture?

I was doing problem 6.3 from here. To make this less programming and more math oriented: GCDMany is equivalent to using Euclid's method (using mods and NOT ...
1
vote
1answer
75 views

Ping Pong Winning Probability (World Series)

You are playing ping pong with a friend and your chance to win any point is P. This is a world series. Find the probability that you score 4 points before your friend has a score of 4. Evaluate this ...
2
votes
3answers
52 views

Why is the inverse of this function not a function?

Why does $F^{-1}$ need to be defined on all of $Y$? I can have this function: $g(x)=x,\quad x\ne 3$ and even though it is not defined for all $x$ in its domain, it is still a function, right?
1
vote
2answers
43 views

How do I calculate variance for sum of dice?

I'll post my work, but I'm not sure how to calculate variance. The question asks for the expected sum of 3 dice rolls and the variance. I think I got the expected sum. Any help would be awesome :) ...
0
votes
1answer
37 views

Is the polar of the polar set the original set?

For each $Q \subset \Bbb R^n$, denote $Q^*:=\{z \in \Bbb R^n:z\cdot x \leq 1,\;\;\text{for all}\; x \in Q\}$. Let $P:=\{x \in \Bbb R^n: Ax \leq b\}$, for the matrix $A$ and the vector $b$. It is ...
1
vote
1answer
125 views

Finding Truth Values Of Nested Quantifiers

I'm looking at for example, $∃x∀y,P(x≥y+1)$ I'm told in order to prove that this is true I can us the technique that follows: Find one value of $x∈X$(only needs to be one) that has the property that ...
0
votes
3answers
63 views

Homework question. please give me hints or feedback

Prove or find a counterexample: For all real numbers x and y it holds that x + y is irrational if, and only if, both x and y are irrational
0
votes
1answer
51 views

Finding formula for a series and proving

Find a formula for $\displaystyle\sum_{i=1}^n \frac{i}{(i+1)!}$ and prove that it holds for all $n \ge 1$. How do you find an equation for this formula? Is it common sense or is there a way to find ...
1
vote
2answers
110 views

Get the Nth term of a sequence 1,2,4,7,13,24…

I have a sequence: 1,2,4,7,13,24,44,81, ... and I think it's like a Fibonacci sequence, however you add three number together and not two ("Tribonacci"?). So: $$ v_n = v_{n-1} + v_{n-2} + v_{n-3} $$ ...
0
votes
1answer
43 views

How can a function not be one to one and be a function?

My understanding of the definition of a function Given any x, there is only one y that can be paired with x My understanding of a 1 to 1 function Given any y, there is only one x that can be paired ...
0
votes
0answers
23 views

What is the general form of a finite sequence?

I originally used: $a_0,a_1,a_2,...,a_n$ where $n$ is an integer greater than or equal to 0 but I've realized that this is actually an infinite sequence because n can go to $\infty$. How can I bound ...
1
vote
1answer
42 views

Combinations and Probability Problems

I try this problem and I got $\binom{50}{20} * \binom{30}{20} * \binom{10}{10} = 1.416 * 10^{21}$ . I just want to make sure I have the right idea for this problem. In a medical experiment involving ...
1
vote
1answer
39 views

Probability and Combinations

In a family with 6 children, a. What is the probability of having three children of each sex? b. What is the probability of having four of one sex and two of the other sex? I know in this problem ...
1
vote
1answer
34 views

How to find a pattern in this recursive sequence algorithmically?

I'm trying to find the closed-form of a sequence algorithmically. Here is the recursive sequence: $$w_k=w_{k-2}+k, \forall k \in \Bbb{Z} | k \geq 3, w_1=1, w_2=2$$ which produces this sequence: ...
1
vote
3answers
67 views

Finding the limit of a sequence by diagonalising a matrix

Consider the sequence described by: $\frac11 , \frac32 , \frac75 , ... ,\frac {a_{n}}{b_{n}}$ where $ a_{n+1} = a_n +2b_n $ and $b_{n+1} = a_n+b_n$ Find a matrix $A$ such that ...
0
votes
1answer
29 views

three things question Discrete math on multipartite graph

I am wonder about these problem 1.Degree sequence of the complete Multi-partite graph $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$ and 2.My class professor said one proposition that If graph is ...
0
votes
1answer
15 views

Discrete math on multipartite graph

I am wonder about these problem 1.The complete Multi-partite graph $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$ 2.the number of edge of $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$
0
votes
2answers
53 views

Number of lines/triangles determined by n points

Can someone please illustrate how this plane works by drawing. I just want to get an idea of how this plane works. There are n points in the plane, such that no three points are on the same line. a) ...
0
votes
1answer
51 views

Induction proof that $4^n > 3^n+2^n$ for $n\ge2$

This is a problem with induction and proofs but I'm not sure how to start with proving this one. $$\text{Show that for any $n \geq 2$, $4^n > 3^n+2^n$}$$
0
votes
4answers
102 views

Proof that $(1 + x)^n > 1 + nx$ for $x>-1$, $n$ a positive integer [duplicate]

For any positive integer $n$ and real number $x > -1$, show that $(1 + x)^n > 1 + nx$. This is Bernoulli’s inequality but I can't figure out how to start with this. Can someone help? Thanks
3
votes
1answer
38 views

Where did this “+1” term come from for this inductive proof?

Where did this "+1" term come from for this inductive proof? It is in boxed in black. For context, We are trying to prove this sequence: has the following solution: $$x_{ n }=\frac { 3^{ n+1 ...
0
votes
1answer
72 views

A formula for $\sum^n_{i=1}(1+1/n)$?

Find a formula for $$\sum^n_{i=1}\left(1 + \dfrac{1}{n}\right)$$ Prove that it holds for all $n \geq 1$. It kind of looks like is a series but I didn't succeed in this problem. Can someone help me ...
2
votes
1answer
144 views

Spelling has deteriorated by the year of 2075, how many spellings are possible?

By the year 2075, spelling has deteriorated such that the dictionary now defines the spelling of the word “RELIEF” to be any combination (with repetition allowed) of the letters F, L, R, I and E ...
3
votes
0answers
25 views

(Counting problem) more challenging Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help - Part II after Part I: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ x_1 y_2 = x_2 y_1 \pmod N \qquad (1) \\ ...
2
votes
2answers
86 views

(Counting problem) very interesting Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ (1) \quad x_1 y_2 \equiv x_2 y_1 \pmod{N}\\ (2) \quad x_1 y_3 ...
2
votes
2answers
94 views

Recurrence relation practice problem that I can't figure out

Thanks for taking the time to look at this problem. I'm trying to prepare for a test on Monday by doing some extra odd numbered problems from my textbook. I'm having a lot of trouble trying to solve ...
1
vote
1answer
100 views

Finding the radius of a sphere touching other spheres inscribed in n-dimensional spaces

I know for certain that the radius of the first one is $r=(\sqrt2-1)/2$. I assume the radius of the other dimensions are the same but I don't know how I would create an equation to prove that. Lastly ...
1
vote
3answers
115 views

Draw a finite state machine which will accept the regular expression $(a^2)^* + (b^3)^*$

Draw a finite state machine which will accept the regular expression: $(a^2)^* + (b^3)^*$ In particular, I am confused by the $+$ sign, what does it exactly mean? Most literature I could find about ...
1
vote
2answers
61 views

Induction And Proofs

Find a formula for $\sum_{i=1}^{n} \frac{1}{(2i-1)(2i+1)}$ and prove that it holds for all $n \geq 1$ I don't know how to solve this particular problem, can someone help me please. Thanks
-1
votes
2answers
40 views

Discrete Math: Inductions

Find a formula for $\sum_{i=1}^n \frac{i}{(i+1)!}$ and prove that it holds for all $n\geq 1$. I'm not sure how to go with this problem can someone help please. Thanks
3
votes
4answers
47 views

Is this a correct recursive sequence definition?

Take this definition: Is this definition of $s_k$ for $k\ge2$ correct? $s_k=6a_{k-1}-5a_{k-2}$ but where does the $a$ term come from? The book swaps $a$ and $s$ interchangeably.
1
vote
4answers
82 views

Show that if $p$ is a prime number $> 3$ then $24 \mid p^2-1$ [duplicate]

Hi guys can someone help me with this ?(Without using Modular arithmetic) Show that if $p$ is a prime number $>3$ then $24$ $\mid$ $p^2-1$
6
votes
3answers
83 views

Show that $9\mid a^2$ if given that $6\mid a$

Does this prove I made seem correct to show that if $6$ divides $a$ then $9$ divides $a^2$ If $6\mid a$, then $a = 6k$ (k is some integer). Then $a^2 = 36k^2 = 9(4k^2)$. Which means that $9\mid ...