Explore Discrete Math Examples

How can I recursively define functions of more than one variable?
If I want to recursively define a function $f:\mathbb{N}\to <!--\; \to \; -->\mathbb{N}$, I can follow the following simple schema:
1. Define f(0) explicitly.
2. For each $n\ge <!--\; \ge \; -->0$, define $f(n+1)$ in terms of f(n).
This ensures that each natural number has a unique image under f. Now suppose I want to recursively define a two-variable function $g:\mathbb{N}\times <!--\; \times \; -->\mathbb{N}\to <!--\; \to \; -->\mathbb{N}$. For example, maybe I want to define binomial coefficients, or stirling numbers, or something. Is there an analogous schema I can use?
Note: I'm very new to math, so if you could be as explicit as possible, I would really appreciate it!

Finding X for density function
A city's fire brigade is deployed approximately every 2 days to extinguish a fire. The number of operations X per week is assumed to be Poisson distributed. Calculate the density and the distribution function of the time T that elapses between two fires. Represent both functions graphically.
I have this formula for the density function:
$f(x)=\frac{{\mathrm{\mu <!--\; \mu \; -->}}^x}{x!}\cdot <!--\; \cdot \; -->{\exp }^{-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->}}$
$\mathrm{\mu <!--\; \mu \; -->}=2$ because 2 days pass between fires I think but I am not sure what X should be.

What is the characteristic equation of $a_{n+2}+2a_n=0$?
So if we let $a_n=C{r}^n$ then we have $C{r}^{n+2}+2C{r}^n=C{r}^n(r^2+2)$. So I got that the characteristic equation $r^2+2=0$ but it should be $r^2+2r=0$ apparently.

Number of digits in 1…n
Let n be a positve integer. Consider the task of printing all the numbers from 1 to n. For example, 512 has three digits.
When n is small,the task can be completed quickly; when n is large it can take a long time.
How many digits does it take to print these numbers?

How do you algebraically demostrate that $f(x)=x^3-<!--\; -\; -->x$ is not a one to one function?
So, I'm trying to prove that the function its not one to one, but I'm stuck:
$f(x_1)=f(x_2)\to <!--\; \to \; -->x_1=x_2$ then is a one to one
So $x_1^3-<!--\; -\; -->x_1=x_2^3-<!--\; -\; -->x_2$
$x_1^3-<!--\; -\; -->x_2^3-<!--\; -\; -->x_1+x_2=0$
$(x_1-<!--\; -\; -->x_2)(x_1^2+x_1{x}_2+x_2^2)-<!--\; -\; -->(x_1-<!--\; -\; -->x_2)=0$
$(x_1-<!--\; -\; -->x_2)(x_1^2+x_1{x}_2+x_2^2-<!--\; -\; -->1)=0$
Which is true if $x_1=x_2$ but how do I go about proving that is not a one to one function?

Show that the matrix is a generator matrix of a MDS code
Let $a_1,\dots <!--\; \dots \; -->,a_n$ be pairwise distinct elements of ${\mathbb{F}}_q$ and $k\le n$. I have to show that
1. The matrix $\left[\begin{array}{cccc}1& \dots <!--\; \dots \; -->& 1& 0\\ a_1& \dots <!--\; \dots \; -->& a_n& 0\\ a_1^2& \dots <!--\; \dots \; -->& a_n^2& 0\\ ⋮<!--\; ⋮\; -->& & ⋮<!--\; ⋮\; -->& 0\\ a_1^{k-<!--\; -\; -->1}& \dots <!--\; \dots \; -->& a_n^{k-<!--\; -\; -->1}& 1\end{array}\right]$ is a generator matrix of an $[n+1,k,n-k+2]$ MDS code.
2. if q is a power of 2, then the matrix $\left[\begin{array}{ccccc}1& \dots <!--\; \dots \; -->& 1& 0& 0\\ a_1& \dots <!--\; \dots \; -->& a_q& 1& 0\\ a_1^2& \dots <!--\; \dots \; -->& a_q^2& 0& 1\end{array}\right]$ is a generator matrix of an $[q+2,3,q]$ MDS code.
I don't even know where to start, the things we covered in the lecture are not so many, but what I thought could be useful, but don't know how to apply are:
Theorem: Let C be an [n,k] code with generator matrix G and parity check matrix H. The following are equivalent:
1. C is MDS
2. All $(n-<!--\; -\; -->k)\times <!--\; \times \; -->(n-<!--\; -\; -->k)$ full size minors of H are invertible
3. All $k\times <!--\; \times \; -->k$ full size minors og G are invertibleMaybe I could use this theorem, part (3), but I'm not sure how to show that all the minors og G are invertible.
Should I maybe, from definition of MDS, show that the distance is indeed $d(C)=n-<!--\; -\; -->k+2$, and then conclude that the code is MDS? But aren't the elements arbitrary?
Should I maybe look for a parity check matrix H and do something?

Find the negation of the following quantified sentence $(\forall x)(p(x)\vee q(x)\to \neg q(x))$
My attempt:
To negate a quantified sentence, I just need to change the quantifier and connectives.
So: $(\forall x)(p(x)\vee q(x)\to \neg q(x))$
Denying: $(\exists x)(p(x)\wedge q(x)\wedge q(x))$
$\neg (\forall )=\exists$
$\neg (\vee )=\wedge$
$\neg (\to )=\wedge$
$\neg (\neg q(x))=q(x)$
I'm pretty sure that my solution is correct, the problem is that the denial of the conditional connective is causing me doubts.

Discrete math: given an integer, there are no two integer x,y such that $x>k/2$ and $y>k/2$.
I wanted to ask if the use of quantifier in this proof were correct:
let k be a positive integer. Then $\mathrm{\neg <!--\; \neg \; -->}\mathrm{\exists <!--\; \exists \; -->}x,y$ that are integer and such that $x>k/2\wedge <!--\; \wedge \; -->y>k/2$ and $x+y=k$.
Proof by contradiction: suppose that two such integers x,y existed. Then $x>k/2\wedge <!--\; \wedge \; -->y>k/2$ implies that $x+y>k/2+k/2$ but then $x+y>k$ and so $x+y=k$ would be false.
Therefore, it is true that $\mathrm{\neg <!--\; \neg \; -->}\mathrm{\exists <!--\; \exists \; -->}x,y$ such that $x+y=k$ and $x>k/2\wedge <!--\; \wedge \; -->y>k/2$ and $x+y=k$.

Kenneth Rosen - Discrete Math (product rule and truth table)
I was trying to solve an exercise from Kenneth Rosen - Discrete Math's book. The exercise is the following, and it involves using the product rule:
Use the product rule to show that there are $2^{2^n}$ different truth tables for propositions in n variables.
The solution should be something like this:
We know that since there are two possible ways of assigning a truth value to a propositional variable, given n propositional variables there are $2^n$ possible different assignment of truth values.
Then we can ask ourselves how many different truth table can be built starting from those different assignment.
A truth table can be thought of as a function that takes as argument an assignment of truth values and gives as output another truth value.
For instance, one truth table for p, q, r can be considered as the function t1 that goes from the set of possible assignment for p, q, r of cardinality 8 to the set T,F and it is that function that always assign T and never F. A different truth table of the same variables could be the funciton t2 that for every possible assignment of truth value to p,q,r it always assign T unless p is false, and so on.
So each truth table corresponds to a function from the set of possible different assignment to the set of boolean values T,F.
Since we know that the set of possible assignment for n propositional variables has cardinality $2^n$ and the codomain of the truth table functions is of cardinality 2, then there are $2^{2^n}$ possibile ways of building truth tables for n variables.
Is it correct to consider truth table for n variables as functions that go from the set of possible assignment to the set T,F)

Light bulbs in a rectangular grid
Suppose we have a grid of $5\times <!--\; \times \; -->5$ light bulbs with a switch to each bulb. If we press a switch it toggles all the lights in its row and column. Given any initial configuration, is it possible to make all the lights on or all the lights off by a particular sequence of switches?
I do not remember whether I have read about this problem somewhere or it just came up in my mind by some similar problems. Any hints/suggestions/links are highly appreciated.

Write out the following equation as a power series
I am trying to write the following equation out as a power series:
$\frac{1}{x^2-<!--\; -\; -->3xn+3n^2}$ where $x\in <!--\; \in \; -->\mathbb{R}$ and $n\in <!--\; \in \; -->\mathbb{N}$ such that $x,n>0$. I have noticed that for $n=1$ we have $\frac{1}{x^2-<!--\; -\; -->3xn+3n^2}=3+9x+24x^2+63x^3+...$
would there be a generalized formula for this expression as a power series in terms of x and n?

Prove an equivalence relation: $mRn\iff <!--\; \iff \; -->3m-<!--\; -\; -->5n$ is even
Let R be a relation on the integer set, where mRn iff $3m-<!--\; -\; -->5n$ is an even number. Prove that R is an equivalence relation. Find equivalence class [2].

Proof by contradictions
Theorem: For all a, b, c in $\mathbb{Z}$ $\mathbb{Z}$if a does not divide $b-<!--\; -\; -->c$, then a does not divide b or a does not divide c. Prove by contradiction
I know the first step is to flip the theorem to "there exists a,b,c in $\mathbb{Z}$ such that a does not divide $b-<!--\; -\; -->c$ and a divides b and a divides c" but I am lost as to how to continue the proof.

All possible multi sets out of a 3 element set
We want to know how many possible multi sets can be formed from a set that has only 3 elements.
My try:
If we look at the multiplicities we get:
$\mathrm{\mu <!--\; \mu \; -->}(a_1)=4⟹<!--\; ⟹\; -->\mathrm{\mu <!--\; \mu \; -->}(a_2)=0⟹<!--\; ⟹\; -->\mathrm{\mu <!--\; \mu \; -->}(a_3)=0$, we can do this 3 times. $\mathrm{\mu <!--\; \mu \; -->}(a_1)=3⟹<!--\; ⟹\; -->\mathrm{\mu <!--\; \mu \; -->}(a_2)=1⟹<!--\; ⟹\; -->\mathrm{\mu <!--\; \mu \; -->}(a_3)=0$ we can do this $2\cdot <!--\; \cdot \; -->3$ $2\cdot <!--\; \cdot \; -->3$ times.
However I know there is a faster way. So if we distinguish between the three elements, I guess we can't use $x_1+x_2+x_3=4$, with formula $(\genfrac{}{}{0ex}{}{n+r-<!--\; -\; -->1}{r})$.
Is it correct if I use stirling number here: S(4,3)

Finding Recurrence
Let be $C_k$, $k^{th}$ Catalam's number and
$f(n)=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})(-<!--\; -\; -->1{)}^{n-<!--\; -\; -->k}{C}_k\text{.}$.
I want to prove the following recurrence:
$f(n+1)+(-<!--\; -\; -->1{)}^n=f(0)f(n)+f(1)f(n-<!--\; -\; -->1)+\cdots <!--\; \cdots \; -->+f(n)f(0)\text{.}$.
I know that there is a similar recurrence involving $C_{n+1}$, that is ${\displaystyle C_{n+1}=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}{C}_{n-<!--\; -\; -->k}{C}_k}$
I wonder if there is a method to prove recurrence, by using Moebius's Inversion Theorem or if there is another way to get recurrence.
Any hints would be really precious, so Thank You very much in advance.

Number of ways to place 25 passengers in the bus with 49 seats with a restriction
A bus has 49 seats divided into 22 pairs of 2 neighbouring seats (numbers $1-<!--\; -\; -->44,$, the neighbouring seats are (1, 2), (3, 4),…,(43, 44), while (2, 3) are separated seats) and 5 seats in the end of the bus.
The passengers are sitting according to a greedy algorithm: if there is nobody sitting on the seats numbered $45-<!--\; -\; -->49,$, a passenger sits on one of those. Otherwise, they sit on one of the first 44 seats with an empty neighbouring seat. If there are none of free pairs of seats, an there is only one person sitting in the end of the bus, they sit on the remaining seats in the end. If there are no free pairs of seats and there are at least 2 people in the end of the bus,a passenger finds any free seat.
In how many different ways can we place passengers in the bus? Note: it is not important if a person A sat on the seat number 1 before a person B sat on the seat number 3 and vice-versa.

If G is n regular, then G has n disjoint perfect matchings.
Let G be a bipartite simple graph show that:
If G is n regular, then G has n paarwise disjoint perfect matchings.
It's firstly easy to show that G has a perfect matching by using Hall’s Theorem, $|N(S)|\ge <!--\; \ge \; -->|S|$ with N the potential mathings and S a arbitary subset of one part of the bipartite graph G. But how to show that there is n perfect matchings and besides disjoint. I've seen a answer by multiplying d to $|N(S)|\ge <!--\; \ge \; -->|S|$, but I don't why should we do this. If anyone could help me with some tipps, I would be very grateful.

N invitations in Rashida's Birthdays
Rashida wanted to invite her friends to her birthday and she was born in April. In a leap year, she started sending invitations from February 16 and completed them by March 15. At least one invitation was sent each day but no more than 50 invitations in total. Therefore, there has been a specific consecutive of days where exactly N invitations had to be sent. What is the value of N?
I started solving this problem in this way. As the year is a leap year, so February month has 29 days. So from February 16 to March 15, there are 28 days. At least one invitation was sent each day but no more than 50 invitations in total.
Therefore, there has been a specific consecutive of days where exactly N invitations had to be sent. I think the number is 8. Is this assumption correct?

Prove that the following set A is countable: A consists of all infinite sequences, $a_0,a_1,...$ that are monotone and such that for every $i=0,1,...,a_i\in <!--\; \in \; -->\{0,1,2\}$