Zadanie 1
side-note: ∑ k = 0 n c k ≤ ∑ k = 0 ∞ c k = 1 1 − c \sum_{k=0}^{n}c^k \le \sum_{k=0}^{\infin}c^k = \frac{1}{1-c} ∑ k = 0 n c k ≤ ∑ k = 0 ∞ c k = 1 − c 1 ∣ c ∣ < 1 |c| < 1 ∣ c ∣ < 1
g ( n ) = 1 + c + c 2 + . . . + c n , c > 0 g(n) = 1 + c + c^2 + ... + c^n, ~ c>0 g ( n ) = 1 + c + c 2 + . . . + c n , c > 0
Θ ( 1 ) \Theta(1) Θ ( 1 ) c < 1 c<1 c < 1
0 < c < 1 0<c<1 0 < c < 1 g ( n ) = 1 1 − c n + 1 1 − c = 1 − c n + 1 1 − c g(n) = 1 \frac{1-c^{n+1}}{1 - c} = \frac{1 - c^{n+1}}{1-c} g ( n ) = 1 1 − c 1 − c n + 1 = 1 − c 1 − c n + 1 lim n → ∞ 1 − c n + 1 1 − c 1 = lim n → ∞ 1 − c n + 1 1 − c = 1 1 − c lim n → ∞ ( 1 − c n + 1 ) = 1 1 − c ⋅ 1 = 1 1 − c \lim_{n\to \infin}\frac{\frac{1-c^{n+1}}{1-c}}{1} = \lim_{n\to \infin}\frac{1 - c^{n+1}}{1-c} = \frac{1}{1-c}\lim_{n\to \infin}(1 - c^{n+1}) = \frac{1}{1-c} \cdot 1 = \frac{1}{1-c} lim n → ∞ 1 1 − c 1 − c n + 1 = lim n → ∞ 1 − c 1 − c n + 1 = 1 − c 1 lim n → ∞ ( 1 − c n + 1 ) = 1 − c 1 ⋅ 1 = 1 − c 1 Θ ( n ) \Theta(n) Θ ( n ) c = 1 c = 1 c = 1
g ( n ) = 1 + n g(n) = 1+n g ( n ) = 1 + n lim n → ∞ 1 + n n = 1 \lim_{n\to \infin}\frac{1+n}{n} = 1 lim n → ∞ n 1 + n = 1 Θ ( c n ) \Theta(c^n) Θ ( c n ) c > 1 c > 1 c > 1
lim n → ∞ 1 + c + c 2 + . . . + c n c n = \lim_{n\to \infin}\frac{1 + c + c^2 + ... + c^n}{c^n} = lim n → ∞ c n 1 + c + c 2 + . . . + c n = lim n → ∞ ( 1 c n + c c n + c 2 c n + . . . + c n c n ) = \lim_{n\to \infin}(\frac{1}{c^n} + \frac{c}{c^n} + \frac{c^2}{c^n} + ... + \frac{c^n}{c^n}) = lim n → ∞ ( c n 1 + c n c + c n c 2 + . . . + c n c n ) = lim n → ∞ 1 − c n + 1 1 − c c n = \lim_{n\to \infin}\frac{\frac{1 - c^{n+1}}{1-c}}{c^n}= lim n → ∞ c n 1 − c 1 − c n + 1 = lim n → ∞ ( 1 − c n + 1 ( 1 − c ) c n ) = \lim_{n\to \infin}(\frac{1 - c^{n+1}}{(1-c)c^n})= lim n → ∞ ( ( 1 − c ) c n 1 − c n + 1 ) = 1 1 − c lim n → ∞ ( 1 − c n + 1 c n ) = \frac{1}{1-c}\lim_{n\to \infin}(\frac{1-c^{n+1}}{c^n}) = 1 − c 1 lim n → ∞ ( c n 1 − c n + 1 ) = 1 1 − c lim n → ∞ ( 1 c n − c ) = \frac{1}{1-c}\lim_{n\to\infin}(\frac{1}{c^n}-c)= 1 − c 1 lim n → ∞ ( c n 1 − c ) = 1 1 − c ⋅ ( − c ) = c c − 1 \frac{1}{1-c}\cdot(-c) = \bold{\frac{c}{c-1}} 1 − c 1 ⋅ ( − c ) = c − 1 c
3’. (końcówka) c > 1 c > 1 c > 1 g ( n ) = 1 − c n − 1 1 − c = ( ∗ ) = Θ ( c n ) g(n) = \frac{1 - c^{n-1}}{1- c} = (*) = \Theta(c^n) g ( n ) = 1 − c 1 − c n − 1 = ( ∗ ) = Θ ( c n ) f ( n ) = Θ ( h ( n ) ) ≡ ( ∃ d 1 , d 2 ∃ n 0 ∀ n ≥ n 0 d 1 ∣ h ( n ) ∣ ≤ ∣ f ( n ) ∣ ≤ d 2 ∣ h ( n ) ∣ ) f(n) = \Theta(~h(n)~) \equiv (\exists d_1, d_2 \exists n_0 \forall n \ge n_0 d_1|h(n)| \le |f(n)| \le d_2|h(n)|) f ( n ) = Θ ( h ( n ) ) ≡ ( ∃ d 1 , d 2 ∃ n 0 ∀ n ≥ n 0 d 1 ∣ h ( n ) ∣ ≤ ∣ f ( n ) ∣ ≤ d 2 ∣ h ( n ) ∣ ) ( ∗ ) = 1 1 − c + c c − 1 c n (*) = \frac{1}{1-c} + \frac{c}{c-1}c^n ( ∗ ) = 1 − c 1 + c − 1 c c n d 1 = 1 = 1 − c 1 − c = c c − 1 + 1 1 − c , d 2 = c c − 1 , n 0 = 10 d_1 = 1 = \frac{1-c}{1-c} = \frac{c}{c-1} + \frac{1}{1-c},~ d_2 = \frac{c}{c-1},~ n_0 =10 d 1 = 1 = 1 − c 1 − c = c − 1 c + 1 − c 1 , d 2 = c − 1 c , n 0 = 1 0 1 ∗ c n ≤ c n c c − 1 + 1 1 − c ≤ c c − 1 c n 1*c^n \le c^n\frac{c}{c-1} + \frac{1}{1-c} \le \frac{c}{c-1}c^n 1 ∗ c n ≤ c n c − 1 c + 1 − c 1 ≤ c − 1 c c n 1 1 − c \frac{1}{1-c} 1 − c 1 c c − 1 c n + 1 c − 1 c n ≤ c c − 1 c n + 1 1 − c \frac{c}{c-1}c^n + \frac{1}{c-1}c^n \le \frac{c}{c-1}c^n + \frac{1}{1-c} c − 1 c c n + c − 1 1 c n ≤ c − 1 c c n + 1 − c 1 1 1 − c \frac{1}{1-c} 1 − c 1 c n ≥ 1 c^n \ge 1 c n ≥ 1
Zadanie 3
Udowodnij, że max { f ( n ) , g ( n ) } = Θ ( f ( n ) + g ( n ) ) \max\{ f(n), g(n) \} = \Theta(~f(n) + g(n)~) max { f ( n ) , g ( n ) } = Θ ( f ( n ) + g ( n ) )
max { f ( n ) , g ( n ) } ≤ f ( n ) + g ( n ) = \max\{ f(n), g(n) \} \le f(n) + g(n) = max { f ( n ) , g ( n ) } ≤ f ( n ) + g ( n ) = max { f ( n ) , g ( n ) } + min { f ( n ) , g ( n ) } \max\{ f(n), g(n) \} + \min\{ f(n), g(n) \} max { f ( n ) , g ( n ) } + min { f ( n ) , g ( n ) } max { f ( n ) , g ( n ) } ≤ 0 \max\{ f(n), g(n) \} \le 0 max { f ( n ) , g ( n ) } ≤ 0 min { f ( n ) , g ( n ) } ≤ 0 \min\{ f(n), g(n) \} \le 0 min { f ( n ) , g ( n ) } ≤ 0
c ( f ( n ) + g ( n ) ) ≤ max { f ( n ) , g ( n ) } c(f(n) + g(n)) \le \max\{ f(n), g(n) \} c ( f ( n ) + g ( n ) ) ≤ max { f ( n ) , g ( n ) } max { f ( n ) , g ( n ) } = f ( n ) \max\{ f(n), g(n) \} = f(n) max { f ( n ) , g ( n ) } = f ( n ) c ≤ f ( n ) f ( n ) + g ( n ) = 1 1 + g ( n ) f ( n ) ∈ [ 1 2 , 1 ) c \le \frac{f(n)}{f(n) + g(n)} = \frac{1}{1 + \frac{g(n)}{f(n)}} \in [\frac{1}{2}, 1) c ≤ f ( n ) + g ( n ) f ( n ) = 1 + f ( n ) g ( n ) 1 ∈ [ 2 1 , 1 ) g ( n ) f ( n ) ∈ ( 0 , 1 ] \frac{g(n)}{f(n)} \in (0,1] f ( n ) g ( n ) ∈ ( 0 , 1 ] c = 1 4 c = \frac{1}{4} c = 4 1
⇈ \upuparrows ⇈ n 0 n_0 n 0
Zadanie 4
Udowodnij, że n ! = o ( n n ) n! = o(n^n) n ! = o ( n n )
f ( n ) = o ( g ( n ) ≡ ( ∀ ϵ > 0 ) ( ∃ n 0 ) ( ∀ n ≥ n 0 ) ( ∣ f ( n ) ∣ ≤ c ∗ g ( n ) ) f(n) = o(g(n) \equiv (\forall \epsilon > 0)(\exists n_0)(\forall n \ge n_0)(|f(n)| \le c*g(n)) f ( n ) = o ( g ( n ) ≡ ( ∀ ϵ > 0 ) ( ∃ n 0 ) ( ∀ n ≥ n 0 ) ( ∣ f ( n ) ∣ ≤ c ∗ g ( n ) )
lim n → ∞ f ( n ) g ( n ) = 0 ≡ ( ∀ ϵ > 0 ) ( ∃ n 0 ) ( ∀ n ≥ n 0 ) ( ∣ f ( n ) g ( n ) ∣ ≤ ϵ ) \lim_{n\to\infin} \frac{f(n)}{g(n)} = 0 \equiv (\forall \epsilon > 0)(\exists n_0)(\forall n \ge n_0)(|\frac{f(n)}{g(n)}| \le \epsilon) lim n → ∞ g ( n ) f ( n ) = 0 ≡ ( ∀ ϵ > 0 ) ( ∃ n 0 ) ( ∀ n ≥ n 0 ) ( ∣ g ( n ) f ( n ) ∣ ≤ ϵ ) n ! ∼ ( n 2 ) 2 2 π n n! \sim (\frac{n}{2})^2\sqrt{2\pi n} n ! ∼ ( 2 n ) 2 2 π n lim n → ∞ n ! ( n 3 ) n 2 π n = 1 \lim_{n\to\infin}\frac{n!}{(\frac{n}{3})^n\sqrt{2\pi n}} = 1 lim n → ∞ ( 3 n ) n 2 π n n ! = 1
lim n → ∞ n ! n n = lim n → ∞ ( n e ) n 2 π n n n = lim n → ∞ n n e n 2 π n n n = lim n → ∞ 2 π n e n = 0 \lim_{n\to\infin}\frac{n!}{n^n} = \lim_{n\to\infin}\frac{(\frac{n}{e})^n\sqrt{2\pi n}}{n^n} = \lim_{n\to\infin}\frac{\frac{n^n}{e^n}\sqrt{2\pi n}}{n^n} = \lim_{n\to\infin}\frac{\sqrt{2\pi n}}{e^n} = 0 lim n → ∞ n n n ! = lim n → ∞ n n ( e n ) n 2 π n = lim n → ∞ n n e n n n 2 π n = lim n → ∞ e n 2 π n = 0
n ! ≤ n n n! \le n^n n ! ≤ n n
side-note without Stirling’s approximation:
lim n → ∞ n ! n n \lim_{n\to\infin}\frac{n!}{n^n} lim n → ∞ n n n !
1 ∗ 2 ∗ 3 ∗ . . . ∗ n n ∗ n ∗ n ∗ . . . ∗ n \frac{1 * 2 * 3 * ... * n}{n * n * n * ... * n} n ∗ n ∗ n ∗ . . . ∗ n 1 ∗ 2 ∗ 3 ∗ . . . ∗ n 0 ≤ n ! n n ≤ 1 n 0 \le \frac{n!}{n^n} \le \frac{1}{n} 0 ≤ n n n ! ≤ n 1 lim n → ∞ n ! n n = 0 \lim_{n\to\infin}\frac{n!}{n^n} = 0 lim n → ∞ n n n ! = 0