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

10
votes
1answer
214 views

Which graphs can be drawn using straight lines with no disjoint edges?

What is the class of graphs that can be drawn using only straight lines with no two edges disjoint? Edges are disjoint when they don't cross and they don't share a vertex. Vertices should be in ...
10
votes
0answers
177 views

A group acting on functions of functions of functions

Given a group acting on a set $X$, there is a standard way to define an action of the group on the set of functions of $X$. This can be extended to the set of functions of functions of $X$ as I show ...
9
votes
9answers
3k views

Set Interview Question, Any Creative Way to solve?

I ran into a simple question, but I need an expert help me more to understand more: The following is True: $ A - (C \cup B)= (A-B)-C$ $ C - (B \cup A)= (C-B)-A$ $ B - (A \cup C)= (B-C)-A$ and ...
9
votes
2answers
2k views

How many bins do random numbers fill?

Given is a sequence $\langle a_1,a_2,\ldots,a_n\rangle$ over the alphabet $\{1,2,\ldots,m\}$ chosen uniformly at random among the $m^n$ possibilities. What is the expected size of the set ...
9
votes
3answers
31k views

Largest prime factor of 600851475143 [duplicate]

I'm trying to use a program to find the largest prime factor of 600851475143. This is for Project Euler here: http://projecteuler.net/problem=3 I first attempted this with the code that goes through ...
9
votes
3answers
798 views

How to prove indirectly that if $42^n - 1$ is prime then n is odd?

I'm struggling to prove the following statement: If $42^n - 1$ is prime, then $n$ must be odd. I'm trying to prove this indirectly, via the equivalent contrapositive statement, i.e. that if $n$ ...
9
votes
3answers
440 views

Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
9
votes
3answers
783 views

Fibonacci numbers divisible by $9$

The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ I want to know how many of the first $1000$ Fibonacci numbers are divisible ...
9
votes
2answers
3k views

What exactly is the difference between weak and strong induction?

I am having trouble seeing the difference between weak and strong induction. There are a few examples in which we can see the difference, such as reaching the $k^{th}$ rung of a ladder and ...
9
votes
3answers
193 views

Show that $2^n(\cos^n(\frac{2\pi}{9})+\cos^n(\frac{4\pi}{9})+\cos^n(\frac{8\pi}{9}))\in\mathbb{Z}$

$a_n=2^n\left[\cos^n\left(\dfrac{2\pi}{9}\right)+\cos^n\left(\dfrac{4\pi}{9}\right)+\cos^n\left(\dfrac{8\pi}{9}\right)\right]$. Show that $a_n\in\mathbb{Z}$ for all $n\in\mathbb{Z}$. Find the last ...
9
votes
3answers
187 views

Is there a closed form or approximation to $\sum_{i=0}^n\binom{\binom{n}{i}}{i}$

I tried to calculate the sum $$ \sum_{i=0}^n\binom{\binom{n}{i}}{i} $$ but it seems that all my known methods are poor for this. Not to mention the intimate recursion, that is $$ ...
9
votes
4answers
2k views

Proof by Induction: Alternating Sum of Fibonacci Numbers [duplicate]

Possible Duplicate: Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer This is a homework question so I'm looking to just be nudged in ...
9
votes
2answers
3k views

Minimum degree of a graph and existence of perfect matching

I was reading a result where the following proposition appears as a preliminary step (and left as exercise): Claim: Suppose $G$ is a graph on $n$ vertices ($n$ even and $n \geqslant 3$) with ...
9
votes
2answers
223 views

How find that $\left(\frac{x}{1-x^2}+\frac{3x^3}{1-x^6}+\frac{5x^5}{1-x^{10}}+\frac{7x^7}{1-x^{14}}+\cdots\right)^2=\sum_{i=0}^{\infty}a_{i}x^i$

let $$\left(\dfrac{x}{1-x^2}+\dfrac{3x^3}{1-x^6}+\dfrac{5x^5}{1-x^{10}}+\dfrac{7x^7}{1-x^{14}}+\cdots\right)^2=\sum_{i=0}^{\infty}a_{i}x^i$$ How find the $a_{2^n}=?$ my idea:let ...
9
votes
4answers
9k views

How would I figure out how many anagrams of mississippi don't contain the word psi?

I'm really confused how I'd calculate this. I know it's the number of permutations of mississippi minus the number of permutations that contain psi, but considering there's repetitions of those ...
9
votes
2answers
13k views

How to convert formula to disjunctive normal form?

Formula is: $((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$ This is what I've already done: $$((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$$ $$(¬(p \wedge q) \vee r) \wedge ((p \wedge q) \vee r)$$ ...
9
votes
4answers
515 views

Help with a recurrence with even and odd terms [duplicate]

I have the following recurrence that I've been pounding on: $$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\ \ \ (\forall n>1)\\ a(2n+1)=a(n)+a(n-1)+1\ \ \ (\forall n\ge 1) $$ I don't have much ...
9
votes
1answer
217 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 ...
9
votes
2answers
501 views

A modified NIM game

Let's play a game of NIM, but with a catch! We have exactly three piles of stones with sizes $a$, $b$ and $c$, all of which are different. We move in turns. In every move, we can select a pile and ...
9
votes
1answer
224 views

What's the most efficient way to put all the stones in one pile?

There are $k$ piles of $n_i$ stones, on every move you can choose two piles with sizes $a$ and $b$ and if $a \ge b$ take from the first pile $b$ stones and put to the second one, on other hand if $a ...
9
votes
1answer
149 views

How and what to teach on a first year elementary number theory course?

In the late 80’s and early 90’s there was the idea of ‘calculus reform’ and some emphasis and syllabus changed. The order of doing things in calculus also changed with the advantage of technology. ...
9
votes
1answer
331 views

Error correction code handling deletions and insertions

I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length. I'm looking for error correction code that would allow me to append one or more ...
9
votes
1answer
114 views

$\{1, 2, . . . , 49\}$ is partitioned into $3$ subsets. Prove that at least $1$ of them contains $3$ different numbers $a,b,c$ such that $a+b=c$

As the title says, I'm asked to prove that at least one of the subsets contains three different numbers $a, b$ and c such that $a + b = c$. I tried to prove it but it is more difficult than it ...
9
votes
1answer
769 views

How to justify the solution of this problem?

Assume $\mathbf{x} \in \mathbb R_+^N$ with support $P=\{p_1,p_2,\cdots,p_K\}$ ($P$ is unknown). We already know that $$f_1(\mathbf{x}) = f_2(\mathbf{x}) = \cdots = f_{N-1}(\mathbf{x})$$ where ...
9
votes
1answer
244 views

Number of ways to write $n$ as sum of odd or even number of Fibonacci numbers

In our discrete mathematics exercises I came of with the question: Prove that the coefficients of $\prod_{n\geq2}{(1-x^{F_n})}=1-x-x^2+x^4+x^7+\dots$ can only be $-1,1$ or $0$, where $F_n$ ...
9
votes
1answer
238 views

Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$

So i was given this question. Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$ Here is my solution: Given $2n$ objects, split them into $2$ groups of $n$, $A$ and $B$. ...
9
votes
1answer
149 views

Interesting shapes using probability and discrete view of a problem

Suppose we have a circle of radius $r$, we show the distance between a point and the center of the circle by $d$. We then choose each point inside the circle with probability $\frac{d}{r}$ , and turn ...
9
votes
1answer
208 views

Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we ...
9
votes
1answer
159 views

Binomial formula for $(x+1)^{1/3}$ (related to Newton's binomial theorem)

I know that $$\displaystyle \sqrt{1+x} = \sum_{j=0}^{\infty}\left( \frac{(-1)^{(j-1)}}{2^{2j-1}\cdot(2j-1)}\binom{2j-1}{j}x^j\right). $$ Now, I want to evaluate $\sqrt[3]{1+x}$ but stuck at some ...
9
votes
2answers
128 views

Why isn't finite calculus more popular?

I'm reading through Concrete Math, and learning about finite calculus. I've never heard of it anywhere else, and a Google search found very few relevant sources. It seems to me an incredibly powerful ...
8
votes
9answers
1k views

prove for all $n\geq 0$ that $3 \mid n^3+6n^2+11n+6$

I'm having some trouble with this question and can't really get how to prove this.. I have to prove $n^3+6n^2+11n+6$ is divisible by $3$ for all $n \geq 0$. I have tried doing $\dfrac{m}{3}=n$ and ...
8
votes
6answers
1k views

If $xy$ and $x+y$ are both even integers (with $x,y$ integers), then $x$ and $y$ are both even integers

The title statement can be proven using the contrapositive, note that $x$ odd or $y$ odd means that at least one of $x\cdot y,x+y$ is odd. Is there a way to prove the statement directly? To ...
8
votes
9answers
2k views

What do we actually prove using induction theorem?

Here is the picture of the page of the book, I am reading: $$P_k: \qquad 1+3+5+\dots+(2k-1)=k^2$$ Now we want to show that this assumption implies that $P_{k+1}$ is also a true statement: ...
8
votes
4answers
2k views

Coin problem with $6$ and $10$

I am doing a coin problem where: In a city where you only have denominations in $6$ and $10$. What is the largest value that this city cannot pay? In another problem that my teacher showed me, ...
8
votes
3answers
1k views

Is it possible to have a rule which generates: 2, 4, 6, 8, 10, 12, 14, 16, -23?

This is on Lagrange Interpolations . . . Is it possible to have a rule which generates the sequence: 2, 4, 6, 8, 10, 12, 14, 16, -23? The hint that he gave us is to use Summation Products, the only ...
8
votes
4answers
22k views

How many distinct functions can be defined from set A to B?

In my discrete mathematics class our notes say that between set A (having 6 elements) and set b (having 8 elements), there are $8^6$ distinct functions that can be formed, in other words: $|b|^{|a|}$ ...
8
votes
3answers
4k views

Questions on “All Horse are the Same Color” Proof by Complete Induction

The following has been bugging me, and I can't go to sleep until I resolve it. Here is a summary of the document on page 109 of http://courses.csail.mit.edu/6.042/spring12/mcs.pdf. False ...
8
votes
3answers
4k views

The number of ways to order 26 alphabet letters, no two vowels occurring consecutively

What is the shortest solution to the following problem? What is the number of ways to order the 26 letters of alphabet so that no two of the vowels a,e,i,o,u occur consecutively? What I ...
8
votes
2answers
276 views

How does $2^{k+1} = 2 \times 2^k$?

I ask only because my textbook infers this in an example. Where should I go to learn more about this? I'm trying to learn mathematics by Induction but my knowledge of simplifying algebraic equations ...
8
votes
2answers
530 views

Is the given relation transitive?

Consider the relation: $$R = \{(a,b), (a,c), (c,c), (b,b), (c,b), (b,c)\}$$ on the set $A = \{a,b,c\}$. Is $R$ transitive? I said no because $$[(c, c) \wedge (a, c)] \Longrightarrow (c,a)$$ is a ...
8
votes
2answers
4k views

What is the difference between necessary and sufficient conditions?

If $\quad p \implies q\quad $ ($p$ implies $q$), then $p$ is a sufficient condition for $q$. If $\quad \bar p \implies \bar q \quad$ (not $p$ implies not $q$), then $p$ is a necessary condition for ...
8
votes
4answers
184 views

Generating functions - deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$

I would like some help with deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$ using generating functions. I have managed to do this for $1^2 + 2^2 + 3^2 +\cdots$ by putting $$f_0(x) = ...
8
votes
4answers
302 views

“How many different integers does this give us?”

How many unique integers can you get from $\lceil2012/n\rceil$ where $n$ is a positive integer? I don't know at all where to begin to approach this problem. I thought it maybe had something to do ...
8
votes
5answers
240 views

How to distinguish between combination and permutation questions?

How do you distinguish combination and permutation question? An example of a combination question: Example: How many different committees of 4 students can be chosen from a group of 15? ...
8
votes
1answer
915 views

Puzzle: Give an algorithm for finding a frog that jumps along the number line

You are playing a game, your goal in this game is to catch a frog that's leaping between natural numbers. At first, the frog is found at the number $a \in \mathbb N$ which is not known to you. Each ...
8
votes
4answers
4k views

what are the applications of the isomorphic graphs?

While studying data structures i was told my instructor that even i am given 3 hour/30 days/3 years to find out whether two graphs are isomorphic or not, it is very very complex and even after ...
8
votes
1answer
75 views

How many rectangles are there on an $8 \times 8$ checkerboard?

How many rectangles are there on an $8 \times 8$ checkerboard? \begin{array}{|r|r|r|r|r|r|r|r|} \hline & & & & & & & \\ \hline & & & ...
8
votes
5answers
210 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 ...
8
votes
6answers
344 views

Can we always draw $n/3$ disjoint triangles from $n$ points in the plane in general position?

Suppose we are given $n$ points in the plane, where $n$ is a multiple of $3$ and no three of these points lie on a line. Is it possible to group all of these points into sets of three, so that if we ...
8
votes
4answers
325 views

Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$

How can I calculate the following sum involving binomial terms: $$\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$$ Where the value of n can get very big (thus calculating the binomial ...