Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie
        LICEUM        

Udowodnij tożsamość

Ciągi wektorowe i liczbowe Szeregi

  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
7 odpowiedzi w tym temacie

#1 Kinia7

Kinia7

    Wielki Analityk

  • ^Przyjaciele
  • 2892 postów
401
Instruktor II
  • Płeć:Kobieta

Napisano 18.01.2016 - 11:25

Udowodnij, że dla dowolnych naturalnych n i m prawdziwa jest równość:   \sum_{k=0}^{m-1} \lceil \frac{n-k}{m} \rceil=n
 

  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2102 postów
1006
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 18.01.2016 - 18:17

Ustalmy m i oznaczmy

 

S(n) = m + \sum_{k=0}^{m-1} \lceil \frac{n-k}{m} \rceil= \sum_{k=1}^{m} \lceil \frac{n+k}{m} \rceil

 

Trzeba więc pokazać, że S(n) = m+n \ \ \ \ \ (*)

 

jeśli n = am +b jest wynikiem dzielenia z resztą n przez m, to mamy

 

S(n) = ma + S(b)

 

Wystarczy zatem udowodnić (*) dla n \in \{0, \ldots, m-1 \}

 

Niech c = m -n > 0. Mamy

 

S(n) = \sum_{k=1}^{c} \lceil \frac{n+k}{m} \rceil + \sum_{k=c+1}^{m} \lceil \frac{n+k}{m} \rceil = c + 2 \cdot (m - c) = 2m-c=m+n

 

A to kończy dowód.


  • 2

#3 bronstein

bronstein

    Wielki Analityk

  • +Mods
  • 1069 postów
324
Instruktor I
  • Płeć:Mężczyzna

Napisano 18.01.2016 - 20:48

 

 

 \sum_{k=1}^{c} \lceil \frac{n+k}{m} \rceil + \sum_{k=c+1}^{m} \lceil \frac{n+k}{m} \rceil = c + 2 \cdot (m - c)

 

 

 

Mam pytanko odnośnie tej równości, mógłbyś wyjaśnić dlaczego te sumy są tyle równe?


  • 0

#4 bb314

bb314

    miła suczka

  • $Jr Admin
  • Redaktor
  • 3981 postów
4727
Profesor
  • Płeć:Kobieta

Napisano 18.01.2016 - 22:15

Dowód indukcyjny:
zakładamy, że dla n prawdziwa jest równość    \bl\sum_{k=0}^{m-1} \lceil \frac{n-k}{m} \rceil=n
 
sprawdźmy dla  n:=n+1
P=n+1
 
L=\sum_{k=0}^{m-1} \lceil \frac{n+1-k}{m}\rceil=\lceil \frac{n+1}{m}\rceil+\sum_{k=1}^{m-1} \lceil \frac{n+1-k}{m}\rceil=\[\ \\\ \\k:=k+1\\\ \\\ \]=\lceil \frac{n+1}{m}\rceil+\sum_{k=0}^{m-2} \lceil \frac{n-k}{m}\rceil=
\ \ \ =\lceil \frac{n+1}{m}\rceil+\sum_{k=0}^{m-1} \lceil \frac{n-k}{m}\rceil-\lceil \frac{n+1-m}{m}\rceil=n+\lceil \frac{n+1}{m}\rceil-\lceil \frac{n+1-m}{m}\rceil=n+\lceil \frac{n+1}{m}\rceil-\lceil \frac{n+1}{m}-1\rceil=
\ \ \ =n+\lceil \frac{n+1}{m}\rceil-\(\lceil \frac{n+1}{m}\rceil-1\)=n+\lceil \frac{n+1}{m}\rceil-\lceil \frac{n+1}{m}\rceil+1=n+1 \gr\ \Rightarrow\ \re L=P
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \   :shifty: \   :shifty:

  • 2

\ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ Jeśli chcesz powiedzieć \ \ DZIĘKUJĘ \ \ lub \ \ ŁAŁ \ \  to zaloguj się i kliknij znak\ rep_up.png\ nad kreską.\bl\ \ \ \nearrow
..
..
..
..
..
..


#5 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2102 postów
1006
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 18.01.2016 - 23:32

Mam pytanko odnośnie tej równości, mógłbyś wyjaśnić dlaczego te sumy są tyle równe?

Tak, wszystkie wyrazy pierwszej sumy są równe 1, a wszystkie wyrazy drugiej sumy są równe 2 :)

 

 

Dowód indukcyjny:

 

Żeby to był poprawny dowód indukcyjny to potrzeba jeszcze sprawdzić przypadek bazowy i skomentować jakoś co się dzieje z m, skoro indukcję robisz tylko po n :)


  • 1

#6 bronstein

bronstein

    Wielki Analityk

  • +Mods
  • 1069 postów
324
Instruktor I
  • Płeć:Mężczyzna

Napisano 21.01.2016 - 21:57

Im bardziej próbuję to zrozumieć tym więcej pytań mi się pojawia:

 

1. S(n) = m + \sum_{k=0}^{m-1} \lceil \frac{n-k}{m} \rceil= \sum_{k=1}^{m} \lceil \frac{n+k}{m} \rceil

 

Dlaczego pogrubiona część jest prawidłowa?

 

2. Dlaczego z

 

S(n) = ma + S(b)

 

wnioskujesz, że :

 

Wystarczy zatem udowodnić (*) dla n \in \{0, \ldots, m-1 \} ?

 

 

Dziękuję z góry za wyrozumiałość i proszę o wyjaśnienie :)

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

"Żeby to był poprawny dowód indukcyjny to potrzeba jeszcze sprawdzić przypadek bazowy i skomentować jakoś co się dzieje z m, skoro indukcję robisz tylko po n :)"

 

 

Czy wystarczy napisać że m jest ustalone, sprawdzić przypadek bazowy i dalej jak bb~ pokazała jest poprawnie? 


Użytkownik Ereinion edytował ten post 21.01.2016 - 23:00
Nie da się zrobić pogrubienia w trybie matematycznym w ten sposób. Edytuję dla poprawy czytelności.

  • 0

#7 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2102 postów
1006
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 21.01.2016 - 23:07

Im bardziej próbuję to zrozumieć tym więcej pytań mi się pojawia:

 

1. S(n) = m + \sum_{k=0}^{m-1} \lceil \frac{n-k}{m} \rceil= \sum_{k=1}^{m} \lceil \frac{n+k}{m} \rceil

 

Dlaczego pogrubiona część jest prawidłowa?

Mamy bowiem:

 

m + \sum_{k=0}^{m-1} \lceil \frac{n-k}{m} \rceil= \sum_{k=0}^{m-1} \left(\lceil \frac{n-k}{m} \rceil + 1 \right) = \sum_{k=0}^{m-1} \lceil \frac{n-k}{m} + 1\rceil = \sum_{k=0}^{m-1} \lceil \frac{n + m - k}{m} \rceil

 

Podstawiamy j = m - k. Wówczas j zmienia się od m do 1 czyli

 

\sum_{k=0}^{m-1} \lceil \frac{n + m - k}{m} \rceil = \sum_{j=1}^{m} \lceil \frac{n + j}{m} \rceil

 

Zamieniamy j na k i gotowe.

 

 

 

2. Dlaczego z

 

S(n) = ma + S(b)

 

wnioskujesz, że :

 

Wystarczy zatem udowodnić (*) dla n \in \{0, \ldots, m-1 \} ?

 

Bo jeśli to udowonię, to mam S(b) = b + m czyli wtedy S(n) = ma + b+ m = n+ m czyli to co chciałem :)

 

Gdyby coś jeszcze było niejasne, to pytaj śmiało.


  • 1

#8 bronstein

bronstein

    Wielki Analityk

  • +Mods
  • 1069 postów
324
Instruktor I
  • Płeć:Mężczyzna

Napisano 03.02.2016 - 17:10

Dzięki za cierpliwość. 

 

Nie wiem skąd czerpiesz takie fajne podejścia do zadań ale jest to bardzo inspirujące.


  • 0





Tematy podobne do: Udowodnij tożsamość     x