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

learn more… | top users | synonyms

0
votes
1answer
8 views

Prove that for all elements n that are member on set N, 0*1 + 1*2 + 2*3 +…+ n(n+1) = n(n+1)(n+2)/3

The problem is :Prove that for all elements n that are member on set N, 0*1 + 1*2 + 2*3 +....+ n(n+1) = n(n+1)(n+2)/3 I have established a base case for n=0, 0*1 = 0(0+1)(0+2)/3 = 0 I have also ...
1
vote
1answer
18 views

How to guess an explicit formula using iteration

EDIT: Adding in more information that is hopefully useful. This is part of a multi step question I'm trying to answer for my homework. First we were given a1 = -3 and a formula ak+1 = ak -1, for all ...
0
votes
3answers
22 views

Proving that function $f:[0,\infty)\rightarrow [0,\infty)$ defined by $f(x)=\frac{x^2}{1-x}$ is bijective.

I am having a bit of trouble with the algebra for proving that the function is injective. Basically I set $f(a)=f(b)$ for $a,b\in[0,\infty)$ and $a,b\neq 1$. ...
1
vote
1answer
42 views

How do I do this summation?

$$\sum_{i=0}^{N-2}\frac{(N-2)!(i+1)(i+2)(i+4)}{2(N-2-i)!N^{i+1}}$$ The answer is N.
0
votes
1answer
20 views

Statistics with discrete math

I am working on a homework problem and I think that I am doing this correctly but i am not sure. This is the question: An upper-level math class has 13 students: 4 of them are females. Two of the ...
1
vote
3answers
69 views

how many even functions are there?

If $A=\{-n,-n+1, \dots, n-1,n \}$, how many functions $A \to A$ are there,that are even,so they satisfy the condition $f(-x)=f(x), \forall x \in A$? Is it maybe $(\frac{|A|}{2})^{|A|}$ ?
0
votes
1answer
12 views

how many arrays exist with specific elements?

How many $m \times n$ arrays exist with elements $0,1 \text{ or } 3$? I thought that there are $(m \cdot n)^3$ arrays,but I am not sure..Could you tell me if it is right?
0
votes
2answers
24 views

Why are there $n^m$ such functions?

A function from the set $A$ to the set $B$ is just a correspondance from each element of the set $A$ to an element of $B$.If $|A|=m$ and $|B|=n$,how many such functions exist?I saw that the solution ...
2
votes
0answers
13 views

Finding the number of relations on set S

I know the number of reflexive relations on a finite set is: $2^{n^{2}-n}$ The number of symmetric relations is: $2^{n+1 \choose 2} $ The number of antisymmetric relations: $2^{n}3^{n \choose 2}$ ...
0
votes
0answers
23 views

Removing backups in an exponential fashion

Background: I want to create a backup system that utilizes the full space of a hard-disk. Given that all backups are approximately equal in size this means that I can save a fixed amount of backups. ...
0
votes
2answers
30 views

Proving the statement?

In the case, if the statement is true, prove it, if false, give a counterexample. $$\forall a,b \in \mathbb N^+, 3| (a^2+b^2) \implies 3 |a \land 3|b$$ How do I prove this?
-1
votes
1answer
11 views

Find closed form solutions for these linear recurrences [on hold]

Find closed form solutions for these linear recurrences Number 1: $f(0)=3$ $f(1)=4$ $f(2)=14$ $f(n)=4f(n−1)−f(n−2)−6f(n−3)$ Number 2: $f(0)=5$ $f(1)=−4/9$ $f(n)=−f(n−1)+2f(n−2)+n$
0
votes
1answer
30 views

Proving Recurrence $A_n \le \sqrt2 + {1\over{2^n}}$ [on hold]

Given recurrence: $$A_0=2$$ $$A_n={A_{n-1}\over2} + {1\over A_{n-1}}~\text{for}~n\ge1$$ Prove $A_n \le \sqrt2 + {1\over{2^n}}$ for all $n\ge0$.
-2
votes
1answer
31 views

Exercise in discrete math [on hold]

Find $q$ and $r$ as defined in the Division Algorithm when $a = 549$ and $b = 236$ Define $f : \mathbb{N} \setminus \{1\} \to \mathbb{N}$ by setting $f(n)$ equal to the largest prime divisor of $n$. ...
1
vote
1answer
17 views

calculate the number of different lottery columns

How many different lottery columns exist(of length $13$,with $1,2 \text{ or } X \text{ at each position}$) ? I have to use this theorem: Let $k$ a natural number and $E$ the set of all different ...
1
vote
0answers
22 views

How many decimal integers can be written?

Using the theorem,I am asked to answer the question,that I have written under the theorem. Let $k$ a natural number and $E$ the set of all different $(x_1,x_2, \dots , x_k)$,where $x_1 \in E_1, ...
0
votes
2answers
16 views

Find $f(n)$ when $n = 2^k$ where $f$ satisfies the recurrence relation $f(n) = f\left(\frac{n}{2}\right) + 1$ with $f(1) = 1$

Given: $f(1) = 1$. Answer: $$f(2) = f(1) + 1 = 1 + 1$$ $$\ldots$$ $$f(4) = f(2) + 1 = 1 + 1 + 1.$$ How do I find the value of $f(n)$ where $n$ is an odd integer? Let say $f(3) = ...
2
votes
2answers
18 views

Finding the recurrence relation for number of ways to deposit n dollars

Question: A vending machine dispensing books of stamps accepts only one dollar coins, 1 dollar bills and 5 dollar bills. a) Find a recurrence relation for the number of ways to deposit n dollars in ...
5
votes
4answers
319 views

What exactly are equivalence classes

What exactly are equivalence classes? Suppose I have an equivalence relation $\sim$ on some set $X$ we denote this as $x \sim y$. The equivalence classes are then $[x] = \{y \in X : y \sim x\}$. ...
0
votes
1answer
46 views

Determine the probability that a randomly selected integer is divisible by one of several integers.

If you choose an element x uniformly at random from the set {1,2,...,100}, what is the probability that x is divisible by 4 or 5? Can someone explain why the answer is 2/5 please, thanks.
2
votes
2answers
51 views

In how many ways we can choose $3$ subsets from set $|S| = 20$ …

In how many ways we can choose $S_1$, $S_2$ and $S_3$ from a set which consists of $20$ element, so that : $S_1 \cap S_2 \cap S_3 = \emptyset$
0
votes
2answers
28 views

how do I figure out Which of the following is true?

I am studying for my exam and I am kind of stuck on this question, how is it that the answer is a)? can someone explain this please. Which one of the following is true? a) $$\sum_{k=0}^{n} ...
2
votes
4answers
57 views

Proving for all n that $\sum_{i=0}^n \frac1{2^{i}} < 2$

Proving for all n $\in \mathbb N$, $$\sum_{i=0}^n \frac1{2^{i}} < 2$$ Hint. First prove that the left hand side can be expressed in closed form, i.e. without using the summation operator. This is ...
0
votes
0answers
26 views

Maximum size of a poset chain

Let m,n ≥ 2. Consider the poset ({1,...,m}×{1,...,n}, ρ) where ρ is defined by (i,j)ρ(k,l) if and only if i ≤ k and j ≤ l. What is the maximum size of a chain in this poset? What is the maximum size ...
0
votes
1answer
8 views

How does one find annihilators for recurrence relations?

I've recently taken an interest in the Method of Annihilators for solving recurrence relations. However, I taught myself using nearly solely this Power Point presentation. Thus, my knowledge is ...
0
votes
0answers
40 views

Thickness of G when G is a simple connected graph

The thickness of a simple graph G is the smallest number of planar subgraphs of G that have G as their union. Show that if G is a connected simple graph with v vertices and e edges, where v ≥ 3, then ...
0
votes
0answers
8 views

How to calculate the combined frequencies of a DCT matrix?

Given a 2D matrix of dimensions w1,h1. I preform a DCT 2D transform on the matrix (DCT = DCT type 2). I get a 2D result matrix. This matrix has two frequency axes - x,y (which are simply the ...
1
vote
1answer
21 views

Pumping lemma contradiction

I have to prove that the language $A_{1}= \{\alpha \in \Sigma^{*}|c^{a}(\alpha)>c^{b}(\alpha) \}$ where $\Sigma=\{a,b\}$, where $c^{a}(a)$ means the number of $a$ in $\alpha$, and $c^{b}(\alpha)$ ...
0
votes
1answer
15 views

choosing poker hand with a specific card

How many ways can you choose at least one A from a deck of card in a poker hand? I just wanted to double check my answer, would it be C(52,5)- C(48,5) Help is much appreciated,
1
vote
2answers
28 views

Different ways of picking a committee of $12$ women and $10$ men

$12$ women and $10$ men are on the faculty. How many ways are there to pick a committee of $7$ if (a) Claire and Bob will not serve together, (b) at least one woman must be chosen I'm not sure ...
0
votes
2answers
22 views

rolling dice 6 times, outcomes showing of 2 sixes

If 6 dices are rolled, in how many ways will exactly 2 sixes show up? I was thinking that it would be 6*6*5*5*5*5, am I right?
0
votes
1answer
38 views

Derive expressions for the formal power series $cos(kz)$ and $sin(kz)$, where $k$ is an arbitrary integer

I'm working on some past exam questions, and I am struggling with the second part of this question: Define the formal power series by the formulas: $$sin(z) = \sum^{\infty}_{n=0} ...
2
votes
0answers
35 views

Taylor approximation of a discrete function

Might be a quite stupid question, I'm not sure: Does Taylor Expansion also work if we have a discrete function. Does a discrete function also have something like a Taylor Expansion? I'd like to ...
1
vote
1answer
21 views

Eulerian connected graph [on hold]

I have a question on grap theory as follows $G=(V,E)$ is a connected graph. Prove that G is Eulerian if and only if there is a partition $E_j$, $j=1,...,m$ of the set of edges such that every $E_j$ ...
0
votes
1answer
20 views

Can't understand trivial discrete logarithm problem

I have a seemingly trivial problem with description: Find all discrete logarithms of base 2 of all non-zero elements in $Z_{11}$ field. I'm basing my learning on the notes I managed to grab ...
0
votes
0answers
23 views

prove splits compatible if and only if edge-split

"Prove that if $e_A$ and $e_B$ are distinct edges of a binary $X$-tree $T$ and $C=A\Delta B$(symmetric difference), then the splits $\sigma(A), \sigma(B)$ and $\sigma(C)$ are compatible if and only if ...
0
votes
1answer
23 views

Proving questions about posets

How do I tackle a proof about posets? I have know idea how to approach this problem. Thanks! Prove that if all subsets of a poset P have least upper bounds, then all subsets of P have greatest lower ...
1
vote
3answers
14 views

Intersection of two sets that contain other sets as elements

How would the intersection of $A=\{a, b, e, \{a, b, c, d\}, \{d, e\}\}$ and $B=\{a, b, c, f, \{a, d\}, \{d, e\}\}$ be defined? I've searched quite a few books but no luck so far.
0
votes
1answer
20 views

Draw all of the nonisomorphic simple graphs which have 5 vertices and 6 edges. [on hold]

How to draw nonisomorphic simple graphs which have 5 vertices and 6 edges? Can you guys please show me how to draw that with an explanation, help will be appreciated. Thanks
0
votes
1answer
61 views

hint to approach this question

2 teams play in total During the course of the game, each team gets points, and thus increases its score by 1. The initial score is 0 for both teams. The game ends when One of the teams gets 25 ...
1
vote
2answers
29 views

Proving that $S_k = \{A \subset \mathbb{N} : |A| = k\}$ for $k\in\mathbb{N}$ is denumerable. [duplicate]

I am having trouble with this problem for quite some time. I posted this question before but I still can not figure out this problem. So far,from the suggestion of user134824, I have tried to define ...
0
votes
2answers
29 views

Probability of selecting one of multiple sets of distinct items

Here is the problem I am having: You have a set of items; let's say colored stones. There are 40 stones. 3 Blue, 3 Red, 3 Green, 3 White, 3 Yellow, 3 Purple, 3 Orange, 1 Black, 18 Grey. Without ...
-4
votes
1answer
37 views

Find a recursive algorithm to find $a^{2^n}$

Edit1: Used Latex. =] Edit2: Thanks for the guidance to the users below. Really helped me out editing the post and guidance on the math problem. The question gave me a hint: $a^{2^{n+1}} = (a^{2^n}) ...
0
votes
1answer
52 views

Proving that these two sets are denumerable.

(a) $S_k=\{A\subset\mathbb{N}: |A|=k\}$ for $k\in\mathbb{N}$ (b) $S = \bigcup_{k=1}^\infty S_k$ Work: For (a), I am not too sure about what approach I should use. I think finding a bijective ...
0
votes
1answer
8 views

Backus-Naur Form with automata

Parsers & compilers usually utilize deterministic finite automata to parse input. It's very easy to implement a generic DFA tool, that simulates any DFA table for example to validate input. ...
0
votes
2answers
20 views

drawing non-isomorphic graphs

I do understand that isomorphic means that they must have the same edges, vertices and adjacency must preserve. Can anyone please just draw a simple example with an explanation. Thanks
0
votes
3answers
30 views

Planar Graph max min edges

Consider a planar graph with 5 vertices, what is the minimum and the maximum number of edges such a graph can have? The graph need not be connected and is simple.
0
votes
2answers
29 views

Gives regular expressions which defines regular language and what does {1,2} mean

The question is give a regular expression which defines a regular language. Question: The language over {0,1} consisting of all strings which either have length less than 3 or have 0 as their third ...
0
votes
1answer
27 views

Prove a statement for the infinite matrix

We are given infinite two dimensional matrix $\{a_{i,j}\}_{i,j=1}^\infty$. And we know that matrix contain only natural values and each number appears in the matrix exactly 8 times. Task is to prove ...
1
vote
4answers
30 views

Help understanding Recursive algorithm question

We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$ For $n\geq0$, let $c(n)$ be the total number of additions for calculating $f(n)$ ...