1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{textcomp}
\usepackage[french]{babel}
\usepackage{amsmath, amssymb}
\usepackage{amsthm}
\usepackage[svgnames]{xcolor}
\usepackage{thmtools}
\usepackage{lipsum}
\usepackage{framed}
\usepackage{parskip}
\renewcommand{\familydefault}{\sfdefault}
\newenvironment{AQT}{{\fontfamily{qbk}\selectfont AQT}}
\usepackage{titlesec}
\usepackage{LobsterTwo}
\titleformat{\section}{\newpage\LobsterTwo \huge\bfseries}{\thesection.}{1em}{}
\titleformat{\subsection}{\vspace{2em}\LobsterTwo \Large\bfseries}{\thesubsection.}{1em}{}
\titleformat{\subsubsection}{\vspace{1em}\LobsterTwo \large\bfseries}{\thesubsubsection.}{1em}{}
\title{TD Maths discrètes}
\author{William Hergès\thanks{Sorbonne Université}}
\begin{document}
\maketitle
\section*{Exercice 1}
Soit $(P_n)_{n\geqslant 2}$ une propriété telle que~:
$$ P_n:\quad \overline{\bigcup^n_{i=0} A_i}=\bigcap^n_{i=0} \bar A_i\quad\land\quad\overline{\bigcap^n_{i=0}A_i}=\bigcup^n_{i=0}\bar A_i $$
$P_2$ est vraie (c'est la loi de de Morgan).
Posons $n\geqslant 2$ tel que $P_n$ soit vraie.
Soient $A_1,\ldots,A_{n+1}$ des parties de $E$.
On pose $B_1=A_n\cup A_{n+1}$ et $B_2=A_n\cap A_{n+1}$.
\begin{align*}
\overline{\bigcup^{n-1}_{i=0} (A_i)\cup B_1} &= \bigcap^{n-1}_{i=0}(\bar A_i) \cup \bar B_1 ~\text{hypothèse de récurrence} \\
&= \bigcap^{n+1}_{i=0} \bar A_i
\end{align*}
de même pour la deuxième partie de $P_n$.
Alors, $P_{n+1}$ est vraie.
Ainsi, $P_n$ est vraie pour tout $n$ supérieur ou égale à 2.
\section*{Exercice 2}
Soient $a\in\mathbb{N}$ et $n\in\mathbb{N}$ tel que $P_a(n)$ soit vraie.
$10^n\times 10 + a = 9\times 10^n + 10^n + a$, donc c'est divisible par $9$ car $9\times 10^n$ l'est et $10^n+a$
l'est aussi par hypothèse.
Alors, $$ P_a(n) \implies P_a(n+1) $$
Prenons le cas particulier $a=9$.
On a que $9 | 10^0 + a \iff 9 | 10$ est faux, donc $P_a(n)$ n'est pas vraie pour tout $n$.
Pour que $P_a(n)$ soit vraie pour tout $n$, il faut que $9|a+1$, i.e. $a=9k+1$ (pour $k\in\mathbb{N}^*$).
\section*{Exercice 3}
$$ P_n:\quad H_{2^n} \geqslant 1+n/2 $$
$P_0:\quad H_1=1 \geqslant 1 + 0/2$
Soit $n$ telle que $P_n$ soit vraie.
On a donc que $H_{2^n} \geqslant 1+n/2$.
\textbf{TODO: refaire}
\section*{Exercice 4}
\begin{enumerate}
\item $F_2=F_1$, donc $P_1$ est vraie.
Soit $n > 0$ tel que $P_n$ soit vraie.
\begin{align*}
F_{2n} &= F_1+\ldots+F_{2n-1} \\
F_{2n+2} &= F_{2n} + F_{2n+1} \\
F_{2(n+1)} &= F_1+\ldots+F_{2n-1} + F_{2n+1}
\end{align*}
Donc $P_{n+1}$ est vraie.
\item[5.] $F_1 \geqslant 0$ et $F_1 \leqslant \varphi$, donc $P_1$ est vraie.
Soit $n>0$ tel que $P_n,\ldots,P_1$ soit vraie.
\begin{align*}
\varphi^{n-2} &\leqslant &F_n& &\leqslant \varphi^{n-1} \\
\varphi^{n-2} + \varphi^{n-3} &\leqslant &F_n+F_{n-1}& &\leqslant \varphi^{n-1} + \varphi^{n-2} \\
\varphi^{n-2} + \varphi^{n-3} &\leqslant &F_{n+1}& &\leqslant \varphi^{n-1} + \varphi^{n-2} \\
\end{align*}
\end{enumerate}
\section*{Exercice 7}
$P(1)$ est vraie, donc $P(2\times 1 = 2^1)$ est vraie.
Donc, $P(2\times 2 = 2^2)$ l'est aussi.
Alors, $P(2^n)$ est vraie par récurrence triviale.
Or, $(2^n)_{n\in\mathbb{N}}$ tend vers $+\infty$.
Soit $k\in\mathbb{N}$, si
\end{document}
|
