\documentclass[a4paper,10pt]{article} \usepackage[T1]{fontenc} \usepackage[polish]{babel} \fontencoding{T1} \usepackage[utf8]{inputenc} \begin{document} \abovedisplayskip=4pt plus 2pt minus 2pt \belowdisplayskip=4pt plus 2pt minus 3pt \def\ss{\vskip10truept} %\baselineskip=.205in \def\prefoot{{\it Lista 1}} \def\postfoot{{\it Strony 1-4}} \font\smr=plr7 scaled\magstep0 \font\hsmr=plr9 scaled\magstep0 \font\srm=plr7 scaled\magstep0 \font\sc=plcsc10 scaled\magstep1 \font\ssrm=plr5 scaled\magstep0 \long\def\rozw#1{} \long\def\odp#1{} \def\coto{Zadania} \def\ln {{\hbox{ln}}} \def\log {{\hbox{log}}} \def\sln {{\hbox{\srm ln}}} \def\slog {{\hbox{\srm log}}} \def\arctg {{\hbox{arctg}}} \def\ssln {{\hbox{\ssrm ln}}} \def\sarctg {{\hbox{\srm arctg}}} \def\sgn {{\hbox{sgn}}} \def\fora{\mathop{\forall}} \def\exi{\mathop{\exists}} \def\maps{\longrightarrow} \def\imply{\Rightarrow} \def\klepsydra#1{\vbox{\hrule\vtop{\hbox{\vrule \strut\thinspace#1\thinspace\vrule}\hrule}}} \def\lub#1#2{\hskip0.0truept\klepsydra{#1}\klepsydra{#2}\hskip3.8truept} \def\luub#1#2{\par\klepsydra{#1}\par\klepsydra{#2}} \def\sss{\vskip 14truept} \newcount\nu \def\nn {{\vskip 8.7truept \bf \the\nu .\ \global\advance\nu by 1}} \def\nx {{\hskip 10truept \bf \the\nu .\ \global\advance\nu by 1}} \def\ny {{\vskip2truept\noindent \bf \the\nu .\ \global\advance\nu by 1}} \def\nz {{\hskip -2truept \bf \the\nu .\ \global\advance\nu by 1}} \nu=1 {\centerline{\large \bf Indukcja matematyczna. Dwumian Newtona.}} \ss \noindent{\small Wykład: zad. 1-4\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Konwersatorium 8.10.2009: zad. 38-40} \noindent{\small /Cwiczenia 6,7.10.2009: zad. 5-37\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Kolokwium nr 1, 13.10.2009: materia/l z zad. 1-40} \sss \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n$ zachodzi r/owno/s/c $$1+4+9+16+\ldots+n^2={n(n+1)(2n+1)\over6}\ .$$ \nn Dowie/s/c, /ze dla dowolnej liczby naturalnej $n\ge 6$ kwadrat (figur/e geometryczn/a) mo/zna podzieli/c na $n$ kwadrat/ow. \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n$ zachodzi nier/owno/s/c $$1000000n<2^n+19000000\;.$$ \nn Dowie/s/c, /ze dla dowolnej liczby naturalnej $n$ oraz dowolnych liczb rzeczywistych dodatnich $a_1,a_2,\ldots,a_n$ zachodzi nier/owno/s/c $$\sqrt[\scriptstyle n]{a_1a_2\ldots a_n}\le{a_1+a_2+\ldots+a_n\over n}\;.$$ %{\Huge Dot/ad wyk/lad} \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n$ zachodzi r/owno/s/c $$1+ 2\cdot 3+ 3\cdot 3^2+ 4\cdot 3^3+ 5\cdot 3^4+...+ n\cdot 3^{n-1}={2n-1\over4}\cdot 3^n+{1\over4}\ .$$ \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n$ zachodzi r/owno/s/c $$(2^{2^0}+1)\cdot (2^{2^1}+1)\cdot (2^{2^2}+1)\cdot (2^{2^3}+1)\cdot (2^{2^4}+1)\cdot...\cdot (2^{2^n}+1)= 2^{2^{n+1}}-1\ .$$ {\bf UWAGA:} $a^{b^c}=a^{(b^c)}$. \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n$ zachodzi r/owno/s/c $$1^3+2^3+3^3+...+n^3=(1+2+3+...+n)^2\ .$$ \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n$ zachodzi r/owno/s/c $$1+ 2\cdot 2+ 3\cdot 2^2+ 4\cdot 2^3+ 5\cdot 2^4+...+ n\cdot 2^{n-1}=(n-1)\cdot 2^n+1\ .$$ \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n\ge2$ zachodzi r/owno/s/c $$ {1\over2}+ {1\over6}+ {1\over12}+ \ldots +{1\over(n-1)\cdot n}=1-{1\over n}\ .$$ \sss {\bf Oznaczenia:} $$\sum\limits_{i=m}\limits^n a_i=a_m+a_{m+1}+a_{m+2}+a_{m+3}+\ldots+a_{n-1}+a_{n}$$ $$\prod\limits_{i=m}\limits^n a_i=a_m\cdot a_{m+1}\cdot a_{m+2}\cdot a_{m+3}\cdot \ldots\cdot a_{n-1}\cdot a_{n}$$ Obliczy/c warto/sci wyra/ze/n: \ny $\displaystyle\sum\limits_{i=3}\limits^5 i^2$ \nx $\displaystyle\sum\limits_{i=-99}\limits^{100} i^3$ \nx $\displaystyle\sum\limits_{i=-10}\limits^{10} 7$ \nx $\displaystyle\prod\limits_{i=1}\limits^{5} i$ \nx $\displaystyle\prod\limits_{i=-2008}\limits^{2008} i^{2008}$ \nn Zapisa/c wzory wyst/epuj/ace w tre/sci poprzednich zada/n bez u/zycia kropek. \nn Liczby $a_n,b_n$ s/a okre/slone wzorami $a_1=b_1=1$, $a_{n+1}=a_n+b_n$, $b_{n+1}=a_{n+1}+a_n$. Dowie/s/c, /ze dla dowolnej liczby naturalnej $n$ liczba $2a_n^2-b_n^2$ jest r/owna $\pm 1$. \vskip 5truept \sss {\sc Oszustwo} \nx Dowie/s/c, /ze dla dowolnej liczby naturalnej $n$ zachodzi nier/owno/s/c $$30n<2^n+110\eqno(*)$$ {\it Rozwi/azanie:} Przeprowadzimy dow/od indukcyjny. $1^\circ$ Dla $n=1$ sprawdzamy bezpo/srednio $30<2+110=112$. $2^\circ$ Za/l/o/zmy, /ze $30n<2^n+110$. Udowodnimy nier/owno/s/c \\ $30(n+1)<2^{n+1}+110$. Stosuj/ac za/lo/zenie indukcyjne otrzymujemy ci/ag nier/owno/sci: $$30(n+1)=30n+30<2^n+110+30= 2^{n+1}+110+30-2^n<2^{n+1}+110,$$ przy czym ostatnia nier/owno/s/c zachodzi dla $n\ge5$. Zatem nier/owno/s/c $(*)$ zosta/la udowodniona dla $n\ge 5$. Pozostaje sprawdzi/c, /ze dla $n=2$ mamy $60<4+110=114$, dla $n=3$ mamy $90<8+110=118$, dla $n=4$ mamy $120<16+110=126$. Tym samym nier/owno/s/c $(*)$ jest udowodniona dla wszystkich liczb naturalnych $n$. W szczeg/olno/sci wykazali/smy, /ze dla $n=6$ zachodzi nier/owno/s/c \\ $180<174$. Gdzie tkwi b/l/ad w powy/zszym rozumowaniu? \ss \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n$ zachodzi nier/owno/s/c $10n<2^n+25$ . \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n\ge2$ zachodzi nier/owno/s/c ${2n\choose n}<4^n$. {\bf Wskaz/owka:} $(1+1)^{2n}$ \nn Wskaza/c tak/a liczb/e $x$, /ze dla dowolnych liczb naturalnych $n$ i $k$ prawdziwa jest r/owno/s/c $$ {n\choose k}+ x{n\choose k+1}+ {n\choose k+2}= {n+2\choose k+2}\;.$$ \nn Uporz/adkowa/c rosn/aco nast/epuj/ace liczby: $$ {100\choose7},\ \ {100\choose27},\ \ {100\choose47},\ \ {100\choose57},\ \ {100\choose77},\ \ {100\choose97}. $$ \nn Rozwi/aza/c r/ownanie $$3\cdot{n\choose4}={k\choose2}$$ w liczbach naturalnych $n\ge4$, $k\ge2$. \nn Dowie/s/c, /ze dla dowolnych liczb ca/lkowitych nieujemnych $a,b,c$ zachodzi r/owno/s/c $$ {a+b+c \choose a} {b+c \choose b}= {a+b+c \choose b} {a+c \choose a}\ .$$ \nn Dowie/s/c, /ze dla ka/zdego $n\ge 2$ zachodzi r/owno/s/c $${2\choose 2}+ {3\choose 2}+ {4\choose 2}+...+ {n\choose 2}= {n+1\choose 3}\ .$$ \nn Dowie/s/c, /ze dla ka/zdego $n\ge 2$ zachodzi r/owno/s/c $${2\choose 2}\cdot {3\choose 2}\cdot {4\choose 2}\cdot...\cdot {n\choose 2}= {n\cdot [(n-1)!]^2\over 2^{n-1}}\ .$$ \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n$ zachodzi nier/owno/s/c ${3n\choose n}<7^n$. \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n$ zachodzi nier/owno/s/c ${2n+3\choose n}<{3\over2}\cdot4^n$. \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n$ zachodzi nier/owno/s/c $${2n+4\choose n}<2^{2n+1}.$$ \nn O zdaniu $T(n)$ udowodniono, /ze prawdziwe jest $T(1)$, oraz /ze dla dowolnego $n\ge6$ zachodzi implikacja $T(n)\imply T(n+2)$. Czy mo/zna st/ad wnioskowa/c, /ze% a) prawdziwe jest $T(10)$,% b) prawdziwe jest $T(11)$,% c) prawdziwa jest implikacja $T(7)\imply T(13)$,% d) prawdziwa jest implikacja $T(3)\imply T(1)$,% e) prawdziwa jest implikacja $T(1)\imply T(3)$.% \nn O zdaniu $T(n)$ udowodniono, /ze prawdziwe s/a $T(1)$ i $T(100)$, oraz /ze dla dowolnego $n\ge10$ zachodzi implikacja $T(n)\imply T(n-1)$. Czy mo/zna st/ad wnioskowa/c, /ze% a) prawdziwe jest $T(9)$,% b) prawdziwe jest $T(10)$,% c) prawdziwa jest implikacja $T(50)\imply T(30)$,% d) prawdziwa jest implikacja $T(300)\imply T(200)$,% e) prawdziwa jest implikacja $T(30)\imply T(50)$,% f) prawdziwa jest implikacja $T(200)\imply T(300)$.% \nn O zdaniu $T(n)$ udowodniono, /ze prawdziwe jest $T(1)$, oraz /ze dla dowolnego $n\ge1$ zachodzi implikacja $T(n)\imply T(n+2)$. Czy mo/zna st/ad wnioskowa/c, /ze% a) prawdziwe jest $T(9)$,% b) prawdziwe jest $T(10)$,% c) prawdziwa jest implikacja $T(100)\imply T(25)$,% d) prawdziwa jest implikacja $T(100)\imply T(200)$.% \nn O zdaniu $T(n)$ udowodniono, /ze prawdziwe s/a $T(1)$ i $T(6)$, oraz /ze dla dowolnego $n\ge1$ zachodzi implikacja $T(n)\imply T(n+3)$. Czy mo/zna st/ad wnioskowa/c, /ze% a) fa/lszywe jest $T(3)$,% b) fa/lszywe jest $T(11),$% c) prawdziwe jest $T(9),$% d) dla dowolnej liczby ca/lkowitej dodatniej $n$ prawdziwe jest $T(n^2)$.% \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n\ge2$ zachodzi r/owno/s/c $$ {1\over6}+ {1\over24}+ {1\over60}+ \ldots +{1\over(n-1)\cdot n\cdot(n+1)}={1\over4}-{1\over 2n(n+1)}\ .$$ \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n$ zachodzi nier/owno/s/c $$ \sum\limits_{i=1}^n i^5<{n^3(n+1)^3\over6} \;.$$ \nn Dowie/s/c, /ze dla dowolnej liczby naturalnej $n\ge 2$ zachodzi r/owno/s/c $$ {1\over 3}+{1\over 8} +{1\over 15} +{1\over 24} +\ldots+{1 \over n^2-1}= {(n-1)(3n+2)\over4n(n+1)}\;.$$ \nn Dowie/s/c, /ze dla dowolnej liczby naturalnej $n$ zachodzi $$ 9\cdot(3n)!\cdot n ............. 2\cdot\left(3^n\cdot n!\right)^3\;.$$ W miejsce kropek wstawi/c jeden ze znak/ow: $>$, $<$, $=$, $\ge$, $\le$. \nn Dowie/s/c, /ze dla ka/zdej liczby naturalnej $n\ge 200$ sze/scian mo/zna podzieli/c na $n$ sze/scian/ow. \nn Wskaza/c sensowne liczby rzeczywiste $A$, $B$, $C$, $D$ i dowie/s/c, /ze dla dowolnej liczby naturalnej $n$ zachodz/a oszacowania $$A\cdot{4^n\over\sqrt{n+B}}<{2n\choose n}