Springen naar inhoud

[Wisk]Waarom: n^2 = U(n-1) + 2n - 1


  • Log in om te kunnen reageren

#1


  • Gast

Geplaatst op 24 november 2005 - 20:24

Het ziet er toch vrij simpel uit, maar ik kom er niet uit. Het is overigens geen huiswerkvraag van mij, maar een vraag naar aanleidig van mijn huiswerk.
Kan iemand het volgende bewijzen:

n^2 = U(n-1) + 2n -1
Waarbij geldt: U(0)=0 en n=(1,2,3....)

directe form. = recurs. formule

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 24 november 2005 - 20:32

Er staat een vergelijking en daarin nog een rij. Die rij zelf definieer je niet, maar als je bedoelt u(n) = n dan is de oplossing triviaal.

u(n-1) + 2n - 1 = (n-1) + 2n - 1 = n - 2n + 1 + 2n - 1 = n

#3


  • Gast

Geplaatst op 24 november 2005 - 20:38

Er staat een vergelijking en daarin nog een rij. Die rij zelf definieer je niet, maar als je bedoelt u(n) = n dan is de oplossing triviaal.

u(n-1) + 2n - 1 = (n-1) + 2n - 1 = n - 2n + 1 + 2n - 1 = n


Huh? Hoe gaat u van de eerste stap naar de 2e? Dan gaat u er toch al vanuit wat juist bewezen moet worden?

#4


  • Gast

Geplaatst op 24 november 2005 - 20:43

Oke ik zal het even anders formuleren...

Ik heb een rij met directe formule R(n)=n^2
En een rij met recursieve formule U(n)=U(n-1) + 2n - 1
U(0)=0
n=(1,2,3....)
Hoe is nu te bewijzen dat deze rijen gelijk zijn aan elkaar?

#5

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 24 november 2005 - 20:53

Ah, dat is duidelijk :roll:

Een bewijs per inductie.

Controle voor n = 1
R(1) = 1 = 1
U(1) = U(0) + 2 - 1 = 1

Inductiehypothese: n = k voldaan
R(k) = k = U(k-1) + 2k - 1 = U(k)

Bewijs voor n = k+1
R(k+1) = (k+1)
U(k+1) = U(k) + 2(k+1) - 1 = k + 2k +2 - 1 = k + 2k + 1 = (k+1)

Q.E.D.

#6


  • Gast

Geplaatst op 24 november 2005 - 21:30

Uit: n2=u(n-1)+2n-1 volgt u(n-1)=n2-2n+1=(n-1)2
Dus u(n)=n2

#7


  • Gast

Geplaatst op 24 november 2005 - 22:08

Bewijs voor n = k+1
R(k+1) = (k+1)
U(k+1) = U(k) + 2(k+1) - 1 = k + 2k +2 - 1 = k + 2k + 1 = (k+1)

N.E.D.

Nu gaat u der al van uit dat U(n) = n^2, doch dit is toch niet gegeven?

#8


  • Gast

Geplaatst op 24 november 2005 - 22:17

Ik zie de verwarring al, sorry voor de blijbaar vage vraagstelling..

U(n)=U(n-1) + 2n -1 met U(0)=0
betekent:

0de term is 0
1e term is 0de term + 2*1 -1
2e term is 1de term + 2*2 -1
3e term is 2de term + 2*3 -1
etc...

#9

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 24 november 2005 - 22:44


Bewijs voor n = k+1
R(k+1) = (k+1)
U(k+1) = U(k) + 2(k+1) - 1 = k + 2k +2 - 1 = k + 2k + 1 = (k+1)

N.E.D.

Nu gaat u der al van uit dat U(n) = n^2, doch dit is toch niet gegeven?

Dat wordt in de inductiehypothese ondersteld.
Een bewijs per volledige inductie gaat in grote lijnen als volgt:
- toon aan dat het voor een zekere waarde van n klopt (gewoonlijk nemen we de kleinst mogelijke)
- veronderstel dat het waar is voor een waarde n = k
- bewijs, uitgaande van die veronderstelling, dat het dan k waar moet zijn voor n = k+1.

Indien je dat laatste kan bewijzen, kan je het toepassen op die kleinst gevonden waarde. Er volgt dan immers dat het ook voor de daaropvolgende moet gelden. Maar daardoor ook weer voor degene die daarop volgt, etc. Via een 'domino-effect' is het dan bewezen voor alle n na die eerste grenswaarde.

#10


  • Gast

Geplaatst op 24 november 2005 - 23:27

J.N. (en eventueel anderen): Wat kan je inbrengen tegen mijn post?

#11


  • Gast

Geplaatst op 25 november 2005 - 18:45

Dat wordt in de inductiehypothese ondersteld.
Een bewijs per volledige inductie gaat in grote lijnen als volgt:
- toon aan dat het voor een zekere waarde van n klopt (gewoonlijk nemen we de kleinst mogelijke)
- veronderstel dat het waar is voor een waarde n = k
- bewijs, uitgaande van die veronderstelling, dat het dan k waar moet zijn voor n = k+1.

Indien je dat laatste kan bewijzen, kan je het toepassen op die kleinst gevonden waarde. Er volgt dan immers dat het ook voor de daaropvolgende moet gelden. Maar daardoor ook weer voor degene die daarop volgt, etc. Via een 'domino-effect' is het dan bewezen voor alle n na die eerste grenswaarde.

Jep, ik snap het. Dank u wel, weer wat geleerd hier :wink: ...volledige inductie-methode...

#12


  • Gast

Geplaatst op 25 november 2005 - 18:47

J.N. (en eventueel anderen): Wat kan je inbrengen tegen mijn post?

Uit.....volgt:..... klopt bij jouw post niet...

#13


  • Gast

Geplaatst op 26 november 2005 - 12:51

Dat moet je even uitleggen!

Trouwens, misschien is het duidelijker als ik zeg dat de gegeven verg helemaal geen recursieve is.

#14


  • Gast

Geplaatst op 27 november 2005 - 01:50

Dat moet je even uitleggen!

Nee, lijkt mij wel correct, hoor.

#15

Safe

    Safe


  • >5k berichten
  • 9906 berichten
  • Pluimdrager

Geplaatst op 01 december 2005 - 23:54

J.N.
Ik ben bang dat ik geen reactie meer krijg en dat is jammer!





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures