# Tagged Questions

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.

2answers
45 views

2answers
40 views

### Prove that $\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$

I have this math question that I'm kind of stuck on. Prove that for all integers $1 < k \le n$, $$\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$$ I have to use mathematical ...
1answer
31 views

### What is the probability of drawing a hearts when the first card you draw was spade? Please check the description

Intuitively we know that when the first card drawn was Spade, it left $13$ hearts and $51$ cards so the probability is $13/51$. I was trying to solve it by the formula of conditional probability P(B|...
3answers
49 views

1answer
132 views

4answers
80 views

### Prove that $(1 + \sqrt2)^{2n} + (1 - \sqrt{2})^{2n}$ is an even integer.

Prove that $(1+\sqrt2)^{2n} + (1-\sqrt2)^{2n}$ is an even integer. I'm not sure how to prove that it is an even integer. What would I do for the Inductive Step? And for the basic step, can I plug in ...
2answers
265 views

### Number of squarefree positive integers less than $100$

An integer is called squarefree if it is not divisible by the square of a positive integer greater than $1$. Find the number of squarefree positive integers less than $100$. My attempt: I apply ...
1answer
49 views

### A binary sequence graph

Define a graph $H(n, 2)$ as follows. Each vertex corresponds to a length $n$ binary sequence and two vertices are adjacent if and only if they differ in exactly two positions. I want to find ...
2answers
43 views

### Prove using induction that $2^n < \binom{2n}{n} < 4^n$ for $n \geq 2$

Trying to prove that, for $n\geq2$, $2^n < \binom{2n}{n} < 4^n$. Inductive hypothesis: Assume $P(k)$ is true: \begin{align} 2^k < \binom{2k}{k} < 4^n \\\\ \end{align} Show $P(k+1)$ \...
1answer
69 views

### Show that for every set of 18 integers there will be two that are divisible by 17 [closed]

I understand the pigeonhole principle is needed here and I see the solution in the back of the book, but the explanation is week. If anyone could explain step-by-step that would be awesome!
2answers
30 views

### Find all non-negative integral solutions $(n_1, n_2, …, n_{14})$ to $\sum^{14}_{i=1} n_i^4 = 1599$.

Find all non-negative integral solutions $(n_1, n_2, ..., n_{14})$ to $\sum^{14}_{i=1} n_i^4=1599$. I have a bit of difficulties to start the problem. Is anyone is able to give me a hint? Please I ...
3answers
63 views

### Two out of five in a group have the same number of friends…

I recently came across a problem- Prove that in a group of five people,there are two who must have the same number of friends in the group. I assume it must be solved by Pigeon Hole Principle (...
2answers
62 views

### Proving $1\cdot1! + 2\cdot2! + 3\cdot3! + … + k\cdot k! = (k+1)! - 1$ [duplicate]

How could one prove by induction that: $$\forall{n}\in{N}:1(1!)+2(2!)+3(3!)+...+n(n!)=(n+1)!-1$$ My attempt so far: Base case: Let n = 1, 1(1!) = (2)! - 1 = 1, holds true for LHS = RHS. Inductive ...
1answer
55 views

### For every partial order ≤ is the relation < transitive?

For every general partial order ≤ is the relation < := ≤ ∩ ≠ transitive I tried working with the definition of the partial order. A partial order is antisymmetric, transitive and reflexive. The ...
1answer
75 views

### Can a number written using one hundreds 0's, one hundred 1's and one hundred 2's be a perfect square? [duplicate]

Question: Can a number written using one hundreds 0's, one hundred 1's and one hundred 2's be a perfect square? I have no idea where to start.
2answers
293 views

### Show that f(x)=e^x from set of reals to set of reals is not invertible…

Yes, this is my question... How can you prove this? That $f(x)=e^x$ from the set of reals to the set of reals is not invertible, but if the codomain is restricted to the set of positive real numbers, ...
1answer
213 views

### Tile a 1 x n walkway with 4 different types of tiles…

Suppose you are trying to tile a 1 x n walkway with 4 different types of tiles: a red 1 x 1 tile, a blue 1 x 1 tile, a white 1 x 1 tile, and a black 2 x 1 tile a. Set up and explain a recurrence ...
2answers
164 views