UL/FRI/UNI-RI/ANA1/Vaje/2006-10-17

Iz E-študij, proste zakladnice študentskega znanja

< UL | FRI | UNI-RI | ANA1 | Vaje
Skoči na: navigacija, iskanje

Vaje z dne 17.10.2006
UL/FRI/UNI-RI/ANA1

Vodil: ni podatka glej podobne vaje

Indukcija

Naloga 1: vsota kvadratov naravnih števil

Poišči polinom p(x) stopnje 3, ki zadošča pogojema

  • njegov prosti člen je enak 0
  • za vsak x velja p(x) − p(x − 1) = x2.
Rešitev 

Predpis p(x) − p(x − 1) = x2 najprej preoblikujemo v p(x) = p(x − 1) + x2. Iz tega predpisa je razvidno, da iščemo polinom, katerega predhodniku smo prišteli x2 oz. polinom, ki bo predstavljal vsoto x2.

Ker je polinom po navodilih 3. stopnje in nima prostega člena, ga lahko zapišemo v obliki:

  • Ax3 + Bx2 + Cx, iz tega potem sledi račun:
  • Ax3 + Bx2 + Cx = x2 + A(x − 1)3 + B(x − 1)2 + C(x − 1), /uredimo
  • Ax3 + Bx2 + Cx = x2 + A(x3 − 3x2 + 3x − 1) + B(x2 − 2x + 1) + C(x − 1)
  • Ax3 + Bx2 + Cx = x2 + Ax3 − A3x2 + A3x − A + Bx2 − B2x + B + Cx − C

Ax3,Bx2 in Cx se krajšajo

  • 0 = x2 − A3x2 + A3x − A − B2x + B − C /preoblikujemo
  • x2 = A3x2 − A3x + A + B2x − B + C

Dobili smo enačbo s 4 neznankami kar ne zgleda najbolje :)

Vseeno je rešitev dokaj enostavna:

Leva stran bo enaka desni takrat, ko bo prvi člen na desni strani(A3x2) enak x2 in preostanek( − A3x + A + B2x − B + C) enak 0.

Prva enačba:

  • x2 = A3x2

Dobimo:

  • A = \frac{1}{3}

Druga enačba:

  • 0 = − A3x + A + B2x − B + C

Vstavimo A in dobimo:

  • 0 = -x+\frac{1}{3}+B2x-B+C

Naslednji pogoj za pravilnost enačbe je odstranitev x.

X se bo krajšal, ko bo B enak \frac{1}{2}

Dobimo:

  • B = \frac{1}{2}

Vstavimo v enačbo:

  • 0 = \frac{1}{3}-\frac{1}{2}+C

Ulomke damo na skupni imenovalec:

  • 0 = \frac{2}{6}-\frac{3}{6}+C
  • 0 = -\frac{1}{6}+C

In dobimo še C:

  • C =\frac{1}{6}

A, B in C sestavimo v polinom in dobimo:

  • p(x) = \frac{x^3}{3}+\frac{x^2}{2}+\frac{x}{6}
  • p(x) = \frac{2x^3}{6}+\frac{3x^2}{6}+\frac{x}{6}
  • p(x) = \frac{2x^3+3x^2+x}{6}

Kar se izkaže, daj je predpis za vsoto kvadratov n zaporednih naravnih števil.

 


Z matematično indukcijo dokaži, da za vsako naravno število n velja formula 

\sum_{i=1}^n i^2 = p(n)
Rešitev 

Dobljeni polinim moramo še dokazati z indukcijo:

Najprej bomo predpis zaradi bolše nazornosti preobilkovali:

Izpostavimo 2x:

  • p(x) = \frac{2x(x^2+\frac{3x}{2}+\frac{1}{2})}{6}

Izračunamo rešitvi nastale kvadratne enačbe(x^2+\frac{3x}{2}+\frac{1}{2})

  • D = b2 − 4ac
  • D = \frac{9}{4} - \frac{8}{4}
  • D = \frac{1}{4}
  • x_1,x_2 = \frac{-b+/-\sqrt[]{D}}{2}
  • x_1 = \frac{-\frac{3}{2}+\frac{1}{2}}{2}
  • x_1 = -\frac{1}{2}
  • x_2 = \frac{-\frac{3}{2}-\frac{1}{2}}{2}
  • x_2 = -\frac{1}{1}

Rešitev:

  • (x+\frac{1}{2})(x+1)

Celoten polinom:

  • p(x) = \frac{2x(x+\frac{1}{2})(x+1)}{6}

2 vnesemo nazaj v prvi ulomek in domimo:

  • p(x) = \frac{x(2x+1)(x+1)}{6}


1.korak - baza indukcije

  • \sum_{i=1}^n i^2 = p(n)

Izračunamo parvilnost računa za n=1:

  • p(x) = \frac{x(x+1)(2x+1)}{6}
  • 1 = \frac{1*2*3}{6}
  • 1 = 1

Baza indukcije je veljavna


2.korak - progresivnost indukcije

p(x)\Rightarrow p(x+1)

Predpostavimo, da lahko p(x) pretvorimo v p(x+1) tako da p(x) prištejemo (x + 1)2

  • p(x+1) = \frac{x(x+1)(2x+1)}{6} + (x+1)^2
  • p(x+1) = \frac{x(x+1)(2x+1)}{6} + \frac{6(x+1)^2}{6}
  • p(x+1) = \frac{x(x+1)(2x+1)+6(x+1)^2}{6}

Izpostavimo (x+1):

  • p(x+1) = \frac{(x+1)(x(2x+1)+6(x+1))}{6}
  • p(x+1) = \frac{(x+1)(2x^2+x+6x+6)}{6}
  • p(x+1) = \frac{(x+1)(2x^2+7x+6)}{6}

Izpostavimo 2 iz drugega oklepaja:

  • p(x+1) = \frac{(x+1)2(x^2+\frac{7}{2}x+3)}{6}
  • D = b2 − 4ac
  • D = \frac{49}{4} - 12
  • D = \frac{1}{4}
  • x_1,x_2 = \frac{-b+/-\sqrt[]{D}}{2}
  • x_1 = \frac{-\frac{7}{2}+\frac{1}{2}}{2}
  • x_1 = -\frac{6}{4}
  • x_1 = -\frac{3}{2}
  • x_2 = \frac{-\frac{7}{2}-\frac{1}{2}}{2}
  • x_2 = -\frac{2}{1}

Rešitev:

  • (x+\frac{3}{2})(x+2)

Celoten polinom:

  • p(x) = \frac{(x+1)2(x+\frac{3}{2})(x+2)}{6}

2 vnesemo nazaj v prvi ulomek in dobimo:

  • p(x) = \frac{(x+1)(2x+3)(x+2)}{6}

Kar je enako:

  • p(x) = \frac{(x+1)(2(x+1)+1)((x+1)+1)}{6}

To pa je isto, kot če bi vsak x v p(x) nadomestili z (x+1).

p(x)\Rightarrow p(x+1)


\frac{x(2x+1)(x+1)}{6} \Rightarrow \frac{(x+1)(2(x+1)+1)((x+1)+1)}{6}

 


Naloga 2

Dokaži, da je za vsako naravno število n\in\mathbb N 

10n − 1

deljivo z 9.

Naloga 3

Poišči formulo za število diagonal v mnogokotniku in jo dokaži z indukcijo.

Naloga 4

Z indukcijo dokaži, da naslednja funkcija max(n) poišče maksimalni element max med števili a_1,a_2,\ldots,a_n. 

funkcija max(k)
  če je k=1, vrni a1
  če je ak > max(k − 1)
    vrni ak
  sicer
    vrni max(k-1)

Naloga 5

Dokaži, da je problem [hanojskih stolpov] vedno rešljiv in izračunaj število potrebnih potez.

Hitro urejanje (domača naloga)

Z matematično indukcijo dokaži, da algoritem za [hitro urejanje] deluje pravilno.

Realna števila, supremum, infimum

Naloga 1

Poišči inf, sup, min in max za naslednje množice števil

  • A=\{x\in \mathbb R; 1<x<2, x ima v decimalnem zapisu le 1 in 2}
  • B=\{x\in \mathbb Q; x^2\le 2\}
  • A=\{x\in \mathbb R; 1<x<2, x ima v decimalnem zapisu le 0, 1 in 2}
  • B=\{x\in \mathbb Q; 2x^3+3\ge 6x+x^2\}

Zaporedja

Naloga 1

Zaporedje je dano z enačbo 

a_n=\frac{n+1}{n+2}.
  • Pokaži, da je \sup \{a_n; n\in \mathbb N\}=1
  • Pokaži, da je limita zaporedja prav tako enaka 1.
  • Za \varepsilon = \frac{1}{10} poišči N iz [definicije zaporedja].
Vzpostavljeno iz »http://www.e-studij.si/UL/FRI/UNI-RI/ANA1/Vaje/2006-10-17«
Osebna orodja
Imenski prostori
Različice
Dejanja
navigacija

Tiskanje/izvoz
orodja