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

0
votes
1answer
21 views

Sum of a recurrence relation

I do know the answer for the $a$ and $b$. The answer for $b$ is $$2^n - 1.$$ But why is that the answer? Isn't the TOTAL price of the nth position $1 + 2 + 2^2 + \ldots + 2^{n-1}$. How does that ...
0
votes
2answers
25 views

Sequence satisfying a recurrence relation

I do understand that recurrence relation is recursion. I understand the idea, but I would just like to know how to prove this. I would really appreciate if you show me how to do this problem and ...
5
votes
1answer
64 views

Writing in 1993, a researcher noted that it is hard to prove things about a cellular automata model - has this changed?

Leah Edelstein-Keshet in her 1993 article Cellular automata approaches to biological modelling writes: We do not believe that CA should be viewed as a replacement for rigorous mathematical models. ...
0
votes
2answers
86 views

Boolean algebra. For all x, y, and z in B, if x + y = x + z and x × y = x × z, then y = z.

In the statements below, $B$ is a Boolean algebra with $\times$ and $+$ for binary operations and ($\bar{a}$)is the complement of $a$. 4.) For all $x$, $y$, and $z$ in $B$, if $x + y = x + z$ and $x ...
1
vote
1answer
33 views

For all $a$ and $b$ in $B$, $(a \times b) + a = a$.

In the statements below, $B$ is a boolean algebra with $×$ and $+$ for binary operations. 3.) For all $a$ and $b$ in $B$, $(a ×b) + a = a$. This is what I have as an answer. Can someone confirm ...
0
votes
1answer
33 views

Why is this a boolean algebra

Let $A = \{a,b\}$. The $\mathcal P(A) = \{\emptyset,\{a\},\{b\},A\}$. Let $+$ be $\cup$, $\cdot$ be $\cap$, complement be set complement, $1$ be $A$, and $0$ be $\emptyset$. I need to explain why ...
12
votes
1answer
1k views

Interview Question Asked In yahoo

Can you find the smallest positive number such that if you shuffle the digits of the number in a particular order, the shuffled number becomes twice the original number. Source: ...
-1
votes
3answers
79 views

mod of minus power 1

I am fully aware on how to perform mod calculation. The issue now is that when I have this $2^{-1} \bmod 10$. How to do this? Is there any formula for this?
1
vote
1answer
35 views

Number of relations from A to B with specific domain

I have two sets $A = \{1,2,3,4\}$, $B = \{5,6,7,8,9\}$ I need to find the number of relations from $A$ to $B$ which includes $\{1,2,3\}$ in the domain. It says to use the Inclusion–exclusion ...
1
vote
1answer
52 views

Proving breath first traversal on graphs [duplicate]

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
0
votes
0answers
55 views

Random looking Gray Codes or Hamiltonian Cycles on Hypercubes

Cyclic Gray codes come in many flavors and correspond 1-1 to Hamiltonian cycles on hypercubes. I would like to find a type that looks like a random walk on the hypercube. In a sense this is an ...
1
vote
1answer
201 views

What is the number of self dual boolean functions?

The dual of a Boolean function $F(x_1,x_2 \dots x_n,+,\bullet)$, written as $F^D$, is the same expression as that of $F$ with $+$ and $\bullet$ swapped. $F$ is said to be self-dual if $F=F^D$. What is ...
0
votes
1answer
76 views

Proofing a Reachable Node Algorithm for Graphs

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
0
votes
2answers
53 views

show that $\det(A)=0$ in this case

(a) Let $x$ and $y$ be $n\times 1$ matrices, $n \ge 1$, and let $A=xy^T$. Show that $\det(A)=0$. (b) Explain why the statment in part (a) is false if $n=1$.
0
votes
1answer
289 views

Size K subset sum problem?

I am trying to solve the following problem - I have a set of $n$ elements consisting of objects say from $O_1$ to $O_n$ ($\{O1_,O_2,O_3,........,O_n$}). Each of those elements are mapped to an integer ...
1
vote
1answer
43 views

$(A \lor B) \implies (((A \lor B) \implies A) \lor ((A \lor B) \implies B))$?

Is the implication in the title true? I haven't studied logic formally yet, so I can't precisely say what A, B exactly are. Perhaps "predicates in first-order logic"?
0
votes
1answer
149 views

G as a graph without self loops and parallel edges with n vertices and m edges

EDITED to include c. Could someone help me understand this problem? I haven't been able to comprehend what I am supposed to do here. 1) Let G be a graph without self loops and parallel edges with n ...
0
votes
3answers
90 views

combination question ASAP required

Hi Can someone help me solve this please? In the clock game Alice and Bob both start at 12 o’ clock. During a move Alice moves 5 hours clockwise on the clock-face and Bob moves 9 hours ...
1
vote
1answer
288 views

Proof using addition and multiplication axioms

I'm working on addition and multiplication axioms of integers for discrete math. I'm trying to prove (k - m) + (m - n) = k - n. The first step I took was this ...
0
votes
1answer
40 views

Find the language of $\sum^*$

For the alphabet $\sum = \{0,1\}$, let $A,B,C \subseteq \sum^*$ be the languages below. $i. A = \{1, 0, 00, 11, 000, 111, 0000, 1111\}$ $ii. B = \{w \in \sum^*|||w|| \ge 2 \}$ $ii. C = \{w \in ...
1
vote
1answer
66 views

need help with Binary Patterns.

Write 0.1, 0.2, and 0.3 in fixed point notation as repeating binary patterns. Use your ability to sum an infinite geometric series ...
1
vote
1answer
43 views

Discrete On Recurrence Sets [duplicate]

Find a recurrence relation for the number of ways to select a subset (any size, including the empty set) from the set {1,2,3, … ,n} that does not contain a pair of consecutive numbers? Would this ...
0
votes
1answer
36 views

Permutations_Combination Discrete

A subset of three distinct positive integers, each less than 20, is selected. a) How many subsets will contain all even integers? b) For how many subsets will the three integers have an even sum? I ...
0
votes
1answer
101 views

Marble Algorithms Using Discrete Math

During a job interview for a computer science job you are hypothetically given two identical marbles and then asked to figure out the following problem. Find an algorithm which minimizes the maximum ...
0
votes
4answers
62 views

Induction Problem

Find a formula for $\sum_{i=1}^n i(i+1)$ and prove that it holds for all $n \geq$ 1. For this induction problem I chose $i = n +1$ so we have $(n+1)(n+1 +1) = (n+1)(n+2)$. Is that what we suppose to ...
-1
votes
1answer
102 views

Recurrence Relation on Finance

a) Find a recurrence relation for the amount of money in a savings account after $n$ months $a_n$, if the interest rate is $.5\%$ interest per month and initially the account has \$$1000$. Solve the ...
0
votes
2answers
142 views

Prove the following Statement is a tautology

I need to prove the following statement is a tautology [¬Q∧(P→Q)]→¬P So far this is what i have but now i am stuck any advice on further finishing this problem would be helpful. ...
1
vote
1answer
56 views

Recurrence Relation all general solutions

I need some help solving the following recurrence relation: $a_n = 4a_{n-1} - 4a_{n-2} + (n+1)*2^n$ What I've tried: a) Find the general solution of the associated linear homogenous recurrence ...
0
votes
1answer
56 views

Help With sets!

Can someone help me solve this question please?? Pretend you are writing traffic accident software and want to categorize accidents by the day of the week on which they occur. Pretend there are n ...
0
votes
1answer
27 views

how to use bit representation in sets?

I'm taking up discrete mathematics this term and I know how to convert integers into binary. but what is the difference if I use bit representation in sets? example: A = {2,4,6,8,10} what is the ...
2
votes
2answers
35 views

Roots of irreducible polynomial over finite field

I have this, and a couple other problems of this kind: For $\mathbb{F}_9=\mathbb{Z}_3[x]/(x^2+1)$, what are the roots of $z^2+1\in\mathbb{F}_9[z]$? I can't figure out, how to start with the ...
1
vote
2answers
260 views

Use the recursive definition of summation together with mathematical induction to prove a sequence

Use the recursive definition of summation together with mathematical induction to prove that for all positive integers $n$ if $a_1, a_2,\ldots, a_n$ are real numbers, then $$\sum_{k=1}^n(3a_k - 2k + ...
0
votes
1answer
74 views

Discrete Math on Recurrence

Consider a $1 \times n$ chessboard. a) Suppose we can color each square of the chessboard either black or white at random. Let $a_n$ be the number of ways to color the chessboard so that no two white ...
0
votes
3answers
73 views

Discrete Math: Induction and Recurrence

Show that the terms of the sequence that satisfy $a_n = 3a_{n-1} - 2$ and $a_1 = 4$ are given by the formula $a_n =3^n + 1$ for all $n \ge 1$. I know this problem has to do with induction. In this ...
1
vote
1answer
46 views

Discrete Math On Recurrence

Suppose that a geometric sequence starts with and satisfies the recurrence $a_n = ra_{n -1}$ for every positive integer $n$. a) Show that $a_n = a_0rⁿ$. b) Find the 100th number in the sequence ...
1
vote
1answer
42 views

Discrete Math On inductions

Show that the sequence defined by the formula a_n = n+3, satisfies the recurrence relation a_n = 2a_n-1 - a_n-2 ,for all n ≥ 2. I know this is a induction problem and I think I have to set n= n+1 ...
1
vote
0answers
67 views

Create a finite-state machine

I need to create a finite-state machine which accepts strings whose characters are in {a,b,c} and produce output strings of T's and F's. The machine outputs a T once the characters ab is encountered ...
0
votes
1answer
35 views

Simplifying Boolean expressions

How do I go about Simplifying the following Boolean expression: AB(A + B)(C + C)? I know (A+B) (A+C)= A+BC but C+C is confusing me.
0
votes
2answers
23 views

Probability help ball question

A bowl contains $5$ red balls, $3$ white, and $2$ blue balls. Two ball are selected without replacement. What is the probability that the two balls are a different colour? The answer that I got is ...
1
vote
1answer
54 views

Confused on how an equation is reached from Concrete Mathematics

I'm reading Concrete Mathematics and trying to understand some of the equations. In particular how the author arrives to a particular solution. Given: $$L_n = \frac{n(n+1)}{2} + 1$$ the author ...
1
vote
2answers
136 views

How to Solve: $2014 ^{2015} \pmod 7$

$$2014^{2015}\pmod 7$$ How do you find the mod of above without using a calculator.
-1
votes
1answer
37 views

Comparing algorithms

Suppose three algorithms are run on a machine that can execute one instruction every microsecond ($10^{-6}$ seconds). They require, respectively, $n \log^2(n)$, $n \log^2(n)+5n$, and $n^2$ operations ...
0
votes
1answer
43 views

Finding conjunctive normal form of a Boolean polynomial

I have to find the conjunctive normal form of the following Boolean Polynomial : $(x_1+x_2+x_3)(x_1x_2+x_1'x_3)'$ I simplified this polynomial to get $x_1x_2'+x_1x_2x_3'$ for which i then formed the ...
1
vote
1answer
37 views

Simplification of a boolean polynomial

I have to simplify the following Boolean polynomial using $x\land y$ = $xy$ and $x\lor y$ = x+y : $xy'+x(yz)'+z$ =$xy'+x(y'+z')+z$ =$xy'+xy'+xz'+z$ =$xy'+xz'+z$ My book gives the following ...
0
votes
1answer
31 views

A question on discrete sequences

Suppose for $1 \leq n \leq M$, we have a discrete sequence $a_n = (1 - 2^{n-M}) \gamma^n$, where $M$ is a fixed strictly positive integer, and $\gamma$ is a fixed strictly positive real number such ...
1
vote
1answer
35 views

Pairwise sums in an ordered list

The scenario: In a game with n players, each player has a in individual score and players are ranked accordingly (P1 is the player/score in 1st place, and Pn is last place). Ties are allowed. Next, ...
0
votes
1answer
376 views

Define a simple hash function..

I am so confused by this.. I am not even sure where to start. Define a simple hash function on strings c = c1c2…cn to be h(key)= (∑_(i=1)^n〖position in alphabet(c_i)〗)mod 10 where the position in the ...
0
votes
1answer
96 views

Partition induced by a Relation

Here's the problem: Let $A=\{1,2,3,4,5,6,7,8,9\}$. Define a relation $R$ on set $A$ by $xRy$ if and only if $2\mid(x+y)$ Assuming that $R$ is an equivalence relation, determine the partition of set ...
0
votes
1answer
468 views

How many edges does a full binary tree with 1000 internal vertices have?

Following my textbooks definition of a full binary tree, which is: If T is a full binary tree with i internal vertices, then T's total vertices = 2i + 1. So with 1000 internal vertices, there would be ...
-1
votes
1answer
26 views

Limits of discrete series.

If a sequence ${b_{n}}$ does not have a limit as n tends to infinity, can I conclude that the series takes on all values in the range of the function. $$b_{n+1}=b_1-\frac{1}{b_n}$$ this series does ...