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
52 views

Multinomial theorem: find the coefficient of $x^3 y^4$ in $(x+2y+3)^{10}$

I have trouble solving this problem: Find the coefficient of $x^3y^4$ in $(x+2y+3)^{10}$ The reason for that I struggle with this problem, is because it has an higher order (10) the $x^3y^4$. ...
2
votes
1answer
37 views

Use induction to prove $\sum_{k=1}^n\frac{k}{2^k}=2-\frac{n+2}{2^n}$

Use induction on $n\in\Bbb N$ to prove that $$\sum_{k=1}^n\frac{k}{2^k}=2-\frac{n+2}{2^n}\;.$$ I have got as far as to the induction step where I have: $$S(n+1)= 2-\frac{n+3}{2^{n+1}}$$ and this ...
3
votes
0answers
48 views

Solution of inhomogenous ODE (4th order)

Hello stackexchangers, I have an inhomogenous ODE in 4th order. This ODE is the constitutive law to describe a material by using the "Wiechert model" (p. 15) which is given by $p_0\sigma + ...
-2
votes
2answers
28 views

Proving a Relation that is a Function by Division Algorithm [duplicate]

Let A=B=$\mathbb{N}$ R is: (a,b)$\in$R iff for some q$\in$Integers a=5q+b WHERE 0$\leq$b<5 Given a relation, show that it's a function. To Show: 1) $\forall$a$\in$A$\exists$b$\in$B((a,b)$\in$R) ...
0
votes
1answer
39 views

Is the relation on integers, defined by $(a,b)\in R\iff a=5q+b$, a function? [closed]

Let $A=B=\mathbb N$. Relation $R$ is: $(a,b)\in R$ iff for some $q \in \mathbb Z$ we have $a=5q+b$ Given a relation, show that it's a function. To Show: $\forall a \in A \ \exists b \in B$ such ...
0
votes
1answer
59 views

Properties of the greatest common divisor: $\gcd(a, b) = \gcd(a, b-a)$ and $\gcd(a, b) = \gcd(a, b \text{ mod } a)$

Prove that (a) gcd(a, b) = gcd (a, b – a) (b) Let r be the remainder if we divide b by a. Then gcd(a, b) = gcd(a, r). I solved part a like: Assume a=pcommonpa b=pcommonpb gcd (a,b) ...
0
votes
3answers
68 views

Modulo: Calculating without calculator??

Calculate the modulo operations given below (without the usage of a calculator): $101 \times 98 \mod 17 =$ $7^5 \mod 15 =$ $12^8 \mod 7 =$ $3524 \mod 63 =$ $−3524 \mod 63 =$ Ok with calculator ...
1
vote
1answer
54 views

Question about problem 53 in Problem Solving and Selected Topics in Number Theory

I solved problem 53 in Problem-solving and selected topics in Number Theory. The problem was: Find the sum of all positive integers that are less than 10,000 and whose square divided by 17 leaves ...
0
votes
1answer
57 views

Prove that every integer from 1 to p – 1 occurs exactly once among these residues.

Let $p$ be a prime and $1 \leq a \leq p-1$. Consider the numbers $a, 2a, 3a, \cdots, (p-1)a$. Divide each of them by $p$, to get residues $r_1,r_2, \cdots,r_{p-1}$. Prove that every integer from $1$ ...
1
vote
2answers
44 views

Whether the graphs G and G' given below are isomorphic

Whether the graphs G and G' given below are isomorphic?
0
votes
1answer
137 views

King Arthur and knights at the round table puzzle

Can you help me with this math problem: Each of the K knights from the round table needs to choose a card which is marked with a number from 1 to N, N >= K. The cards all have different number. ...
0
votes
1answer
72 views

Prove that if p is a prime, a and b are integers

(a) if p | ab, then either p | a or p | b or both. (b) if a | b, p | b, but a is not divisable by p , then p | b/a. I have no problem with the part a I solved that but need some serious help on ...
0
votes
0answers
53 views

Dynamic programming for optimal maximum and optimal minimum

We have a sequence of $a_i$ and a choosing rule that is take the first number $x_t\ge a_t$. The definition is = $$ min\{ t|t \in \{ 1,2,\cdots,n\}\,\,,\,\, x_t\ge a_t\}$$ The sequence $a_i$ is ...
0
votes
1answer
104 views

Use mathematical induction to prove that any integer n>=2 is either a prime or a product of primes.

Use strong mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes. I know the steps of weak mathematical induction... basis step= $p(n)$ for $n=1$ or any ...
1
vote
2answers
30 views

Prove $8n^{3}$ $+$ $√n$ $∈$ $Θ$($n^{3})$

just wondering if I proved this question correctly. Any hints, help, or comments would be appreciated. There are two cases to consider to prove $8n^{3}$ $+$ $√n$ $ϵ$ $Θ(n^{3})$ $8n^{3}$ $+$ $√n$ ...
1
vote
6answers
122 views

The function $G: x \mapsto 2^{x^2}$ maps $\mathbb{R}$ onto $\{ x \in \mathbb{R} : x \geq 1 \}$

Let $X = \mathbb{R}$ and $Y = \{x \in \mathbb{R} :x ≥ 1\}$, and define $G : X → Y$ by $$G(x) = e^{x^2}.$$ Prove that $G$ is onto. Is this going along the right path and if so how do get the ...
0
votes
0answers
26 views

dimension of vector space $\frac{\langle e_{ab_1\ldots b_p}\rangle}{\langle \sum_{1\leq i\leq p}e_{ab_1\ldots \widehat{b_i}\ldots b_pc}\rangle}$

Let $p$ be a prime and $n\!\in\!\mathbb{N}$. What is the dimension of the $\mathbb{Z}_p$-module $$V_{p,n}=\frac{\langle e_{ab_1\ldots b_p};\: 1\leq a<b_1<\ldots<b_p\leq n\rangle}{\langle ...
0
votes
1answer
39 views

Find all real numbers $x$ such that: $\lfloor 7x\rfloor = 7$

I'm not quite sure how to approach this. Does $x$ have to be very small for it to work?
0
votes
1answer
54 views

Big Oh notation involving $\log n!\in O(n\log n)$

I have worked hard on these questions and have found my own approach. I'm just checking if it makes logical sense for others and works. I'd appreciate any hints or better approaches. Question 1: ...
1
vote
3answers
22 views

Let $ a$ be a positive integer. Show that $\text{gcd}(a,a-1) = 1$. use the result of par t $ a)$ to solve the Diophantine equation $ a+b=ab$

Not sure if I did part a right, not sure how to complete part $b)$ $a)$ Let $a$ be a positive integer. Show that $\text{gcd}(a,a-1) = 1$. Proof by contradiction suppose $\text{gcd}(n, n-1) = p > ...
-2
votes
1answer
24 views

Probability: How much days we need to play a game win

Suppose the probability of win a lotery game is : $1/1000$ If a person play the lotery every day with the same combination, how much time he need to wait to win the lotery? Im thinking to use a ...
0
votes
5answers
603 views

Give the number of solutions of $x+y+z = 30$, for $4 \leq x \leq 14$, $3 \leq y \leq 17$, $10 \leq z \leq 25$.

How would I find the number of solutions with both upper and lower bounds? Can anyone give a step by step way to solve this problem? This is question is in preparation for my discrete math final, so ...
7
votes
6answers
111 views

Solve $\lfloor \sqrt x \rfloor = \lfloor x/2 \rfloor$ for real $x$

I'm trying to solve $$\lfloor \sqrt x \rfloor = \left\lfloor \frac{x}{2} \right\rfloor$$ for real $x$. Obviously this can't be true for any negative reals, since the root isn't defined for such. My ...
1
vote
1answer
70 views

Concrete Mathematics Josephus Problem: How to prove 1.17 & 1.18

On the last page of the Josephus problem where things get really general, we're shown the pretty slick radix changing recurrence & solution 1.17 & 1.18 f(j) = aj, for 1 <= j <= d; ...
1
vote
1answer
70 views

Graph and one Sequence challenge

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
2
votes
2answers
33 views

Proof by induction for $ \sum_{n}^{M} \cos(2n) = \frac{\sin(M) \cos(M+1)}{\sin(1)} $

Can someone show me an induction for $$ \sum_{n}^{M} \cos(2n) = \frac{\sin(M) \cos(M+1)}{\sin(1)} $$? My problem is doing that induction with $M$, I am not sure how to proceed to get the right side of ...
1
vote
3answers
56 views

If $A\times B \subset A\times C$, does it follow that $B \subset C$?

On a study guide I have the following question: If $A\times B \subset A \times C$, does it follow that $B \subset C$? Prove or disprove. To me, I think the answer is yes, but I have no idea of ...
0
votes
2answers
175 views

Equivalence relation and equivalence classes

Each bead on a bracelet with three beads is either red, white, or blue. Define the relation R between bracelets as: (B1, B2), where B1 and B2 are bracelets, belongs to R if and only if B2 can be ...
0
votes
1answer
46 views

Prove a functions is injective

Prove the function $f:\mathbb{N} \to\mathbb{N}$defined by $f(x)=2^x$ for all $x$ in $\mathbb{N}$ is one to one. Is my proof correct and if not what errors are there. For all $x_1,x_2$ $\in$$N$, ...
0
votes
2answers
43 views

Matrix rings and ideals

How would one go about checking if a given 2 x 2 matrix is an ideal. I am unclear as to what an ideal is and would like to know the steps in order to make the verification. Also, if it helps, I had ...
0
votes
2answers
47 views

GCD proof using fundamental theorem of arithmetic

prove: $\gcd(m,n)=1$ if and only if $\gcd(m^i,n^r)=1$ I believe you need to do something with fundamental theorem of arithmetic to prove one of the sides. Not quite sure though. Help is appreciated. ...
-2
votes
1answer
49 views

Combinatorial Argument Proof

Prove: $c(40,5) = c(17,5) + c(17,4) + c(23,1) +...+ c(23,5)$ where c is the binomial coefficient. Can I use a combinatorial argument to prove?
0
votes
2answers
51 views

Proof using Induction

Give the induction proof of: $$ k(k+5) = \frac{k}{5} $$ Is this proof even possible? Not sure how to do.
0
votes
1answer
28 views

How to verify an algebraic structure is a ring

I have a problem which ask me to verify that to structures are rings. However, I'm unsure of how exactly to check each property. I believe that the first is closed but not sure how to check the ...
0
votes
1answer
12 views

Clarification on Eulirian cycle proof

I have trouble in understanding this proof can some one clarify the following elements: (1)Why does it follow that if T has maximum length, then $v_0=v_k$?(2)What does E represent?(3)What does E(T) ...
2
votes
2answers
128 views

A Proof for Prime Numbers

Show that among k-digit numbers, one in about every 2.3k is a prime. How can we prove this question? Thanks.
6
votes
1answer
207 views
+500

Minimal “sumset basis” in the discrete linear space $F_2^n$

Let's $$ C\subseteq F^n_2, $$ $$ 2C=C+C=\{\bar\alpha+\bar\beta\ | \bar\alpha,\bar\beta\in C\}. $$ I need to find $C$ such that $2C=F_2^n$ and $|C|$ is minimal. I have found the following ...
1
vote
2answers
39 views

A second order problem on recurrence relation equals 3^n

I had this Recurrence Relation problem: $a_{n+2} + a_{n+1} - 12a_n = 0$ And I solved in a form like this $a_n = A(r_1)^n + B(r_2)^n$ $r^{n+2} + r^{n+1} - 12r^n = 0$ ...
0
votes
0answers
20 views

Formalize: “Every mail message larger then one megabyte will be compressed” [duplicate]

Formalize: Every mail message larger then one megabyte will be compressed
0
votes
2answers
36 views

Define a sequence of integers $H(n)$ by $H(0) = 1$, $H(1) = 3$ and $H(n+1) = H(n) + H(n-1)$?

Then show that $H(n)$ can be expressed in the form $a\cdot(\psi(1))^n + b\cdot(\psi(2))^n$ and that $\psi(1)$ and $\psi(2)$ are the same numbers that occur in the proof of the Fibonacci numbers. I'm ...
0
votes
1answer
29 views

Let A and B be countable sets. Is there any function f such that a certain condition holds for an uncountable number of functions g?

Let $A$ and $B$ be countable infinite sets. Is there any function $f:A\rightarrow B$ such that the number of functions $g:B\rightarrow A$ with property that $g\circ f=\mathrm{id}$ but $f\circ ...
0
votes
2answers
43 views

Combinatorics (discrete math course) help

problem 1: you have 4 balls with different weights and 6 drawers stacked on top of each other. how many ways are there to organize the balls such that the top drawer will have exactly 1 ball and the ...
1
vote
3answers
43 views

Evaluate $\sum_{k=400}^{2000} \frac {2^{3-4k}} {8^{2k+3}}$

Evaluate $$\sum_{k=400}^{2000} \frac {2^{3-4k}} {8^{2k+3}}$$ So far, I was able to get to $$\frac{1}{64}\sum_{k=400}^{2000} \frac {1} {8^{2k}\cdot2^{4k}}$$ And then I'm completely stuck.
0
votes
2answers
36 views

Assign integers to the vertices of $G$

Let $G=(V,E)$ be a directed acyclic graph. I have to write an algorithm to assign integers to the vertices of $G$ such that if there is a directed edge from vertex $i$ to vertex $j$, then $i$ is less ...
1
vote
0answers
31 views

Obtain and prove the rule for divisibility by $ 3$? [duplicate]

I was very confused by this problem, I don't even know what it is asking. Any help would be great :) thanks in advance.
0
votes
2answers
95 views

Justify each step in the proof sequence

$[A \rightarrow ( B \lor C) ] \land B' \land C' \rightarrow A'$ I know how to read the proof sequence, but I don't know what it means to "justify" each step? Does this mean to just state what each ...
3
votes
2answers
70 views

Show that it is the solution of the recurrence

I have to show that the solution of the recurrence $$X(1)=1, X(n)=\sum_{i=1}^{n-1}X(i)X(n-i), \text{ for } n>1$$ is $$X(n+1)=\frac{1}{n+1} \binom{2n}{n}$$ I used induction to show that. I have ...
3
votes
2answers
66 views

Convert form English to logical symbols.

I have a logical argument in English which says. All Humans are Mortal. Zeus is not Mortal. therefore Zeus is not Human. And I tried to convert it from English to logic. and did this h = is ...
3
votes
2answers
49 views

GCD Direct Proof

I want to try and prove this directly because I think it will be more straightforward then a indirect. Also, I believe this has something to do with relatively prime numbers. The help is appreciated! ...
1
vote
1answer
29 views

Proving n is not divisble by m using Division Algorithm

When $n$ and $m$ are integers, how could I write a statement equivalent to the statement "$n$ is not divisible by $m$" using ideas from the Division Algorithm?