matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

For pupils, students, teachers.
Hello Guest!Log In | Register ]
Home · Forum · Knowledge · Courses · Members · Team · Contact
Navigation
 Home...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Tools...
 Agency for private tuition beta...
 Online Games beta
 Search
 Registered Society...
 Contact
Forenbaum
^ Tree of Forums
Status Maths
  Status School
    Status Grades 1-4
    Status Grades 5-7
    Status Grades 8-10
    Status Grades 11-12
    Status Mathematical Contest
    Status School maths - Miscellaneous
  Status University
    Status Uni-Calculus
    Status Uni-LinA u. Algebra
    Status Algebra and Number Theoriy
    Status Discrete Mathematics
    Status Teaching Methodology
    Status Financial Maths and Actuarial Theory
    Status Logic and Set Theory
    Status 
    Status Stochastic Theory
    Status Topology and Geometry
    Status Uni Maths - Miscellaneous
  Status Courses on maths
    Status 
    Status 
    Status Universität
  Status Software for maths
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Calculators

Only forums with an interest level bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
The project is organised by our team of coordinators.
Hundreds of members help out in our moderated forums.
Service provider for this webpage is the Registered Society "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Analysis des R1" - Rekursionsgleichung lösen
Rekursionsgleichung lösen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Analysis des R1"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rekursionsgleichung lösen: .. und beweisen
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 18:55 Di 17.10.2017
Autor: pc_doctor

Aufgabe
Lösen Sie die folgenden Rekursionsgleichungen. Beweisen Sie jeweils die Richtigkeit ihrer Lösung (z.B. durch vollstände Induktion)

a)

T(1) = 0

T(n) = [mm] T(\lfloor\bruch{n}{2}\rfloor) [/mm] + $ [mm] T(\lceil\bruch{n}{2}\rceil) [/mm] $ +n    für n > 1

Sie dürfen annehmen, dass n eine Zweierpotenz ist.



Hallo,

ich habe Probleme bei dieser Aufgabe.

Also normale Rekursionsgleichungen mittels charak. Polynom ist eigentlich kein Problem, aber die Gaußklammern stören mich etwas.

Ich habe mal testweise Werte eingesetzt, um ein System zu erkennn, doch vergebens:

T(1) = 0 ( Rekursionsanker )
-------
T(2) = 2
T(3) = 5
T(4) = 8

T(5) = 12
T(6) = 16
T(7) = 20
T(8) = 24

T(9)  = 29
T(10) = 34
T(11) = 39
T(12) = 44
T(13) = 49
T(14) = 54
T(15) = 59

Ich erkenne, dass für n  = 2,3 und 4 die Differenz immer 3 beträgt

von n = 5 bis 8 ist die Differenz 4

und ab n = 8 bis ?? ist die Differenz 5

Ich werde aber daraus nicht schlau. Oder gibt es einen anderen Ansatz?

Ich würde mich über einen Tipp freuen.

Vielen Dank im Voraus.


        
Bezug
Rekursionsgleichung lösen: Tipp
Status: (Antwort) fertig Status 
Datum: 20:48 Di 17.10.2017
Autor: HJKweseleit

Du solltest den Zahlenwert von [mm] \lfloor log_2(n)\rfloor [/mm] betrachten.

Damit kannst du einerseits die sich ändernden Stufenabstande in den Griff bekommen und andererseits eine Korrektur zu den richtigen Werten finden (dazu brauchst du dann aber [mm] 2^{\lfloor log_2(n)\rfloor}). [/mm]

Bezug
                
Bezug
Rekursionsgleichung lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:58 Di 17.10.2017
Autor: pc_doctor

Danke für den Tipp, mit dem komme ich weiter!

Bezug
                
Bezug
Rekursionsgleichung lösen: Neuer Anlauf
Status: (Frage) beantwortet Status 
Datum: 19:35 So 22.10.2017
Autor: pc_doctor

Hallo,

ich habe mal bisschen anders gerechnet, um die Rekursionsgleichung zu lösen. Ich komme auf log(n), allerdings fehlt da etwas, aber ich weiß nicht was.

Also wir hatten:

T(1) = 0 , das ist der Anker


T(n) = $ [mm] T(\lfloor\bruch{n}{2}\rfloor) [/mm] $ + $ [mm] T(\lceil\bruch{n}{2}\rceil) [/mm] $ +n   für n > 1

Da wir annehmen dürfen, dass n eine Zweierpotenz ist, also so aussieht n = [mm] 2^{a} [/mm] , a [mm] \in \IN [/mm]

Damit ändert sich T(n) zu:

T(n) = [mm] \bruch{n}{2} [/mm] + [mm] \bruch{n}{2} [/mm] + n , für n > 1, n Zweierpotenz.

So, dann versuche ich die Rekursionsgleichung aufzulösen, indem ich immer rekursiv einsetze. Ich setze jetzt also [mm] \bruch{n}{2} [/mm] ein für den Anfang.


[mm] T(\bruch{n}{2}) [/mm] = [mm] T(\bruch{n}{4}) [/mm] + [mm] T(\bruch{n}{4}) [/mm] + n + [mm] \bruch{n}{2} [/mm]

Jetzt setzen wir [mm] \bruch{n}{4} [/mm] ein

[mm] T(\bruch{n}{4}) [/mm] = [mm] T(\bruch{n}{8}) [/mm] + [mm] T(\bruch{n}{8}) [/mm] + n + [mm] \bruch{n}{2} [/mm] + [mm] \bruch{n}{4} [/mm]

=
..

= [mm] T(\bruch{n}{2^k}) [/mm] +  [mm] T(\bruch{n}{2^k}) [/mm]  + [mm] \summe_{i=0}^{k} \bruch{n}{2^k} [/mm]

So, so sieht wohl die Rekursion für k Schritte aus.

Wir setzen [mm] \bruch{n}{2^k} [/mm] = 1
Formen nach k um:

k = [mm] log_2(n) [/mm]  mit k [mm] \le log_2(n) [/mm]

Naja, daraus folgt:

[mm] T(\bruch{n}{2^k}) [/mm] = T(1) = 0

Jetzt müssen wir ja k in die Summe einsetzen, k ist ja k = [mm] log_2(n) [/mm]

Aus der Summe wird nun also [mm] \summe_{i=0}^{log_2(n)} \bruch{n}{2^{log_2(n)}} [/mm] und das ist gleich


[mm] \summe_{i=0}^{log_2(n)} [/mm] 1 = [mm] log_2(n) [/mm] + 1 ( laut Wolframalpha ? )


Also erhalten wir

T(n) = T(1)+ T(1) + [mm] log_2(n) [/mm] +1
T(n) = 0+0+ [mm] log_2(n) [/mm] +1 = [mm] log_2(n) [/mm] +1

Das funktioniert aber irgednwie nicht, wenn ich Testeinsetzungen mache. Wo ist mein Fehler ?

Bezug
                        
Bezug
Rekursionsgleichung lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 20:29 So 22.10.2017
Autor: HJKweseleit


> Hallo,
>  
> ich habe mal bisschen anders gerechnet, um die
> Rekursionsgleichung zu lösen. Ich komme auf log(n),
> allerdings fehlt da etwas, aber ich weiß nicht was.
>  
> Also wir hatten:
>  
> T(1) = 0 , das ist der Anker
>  
>
> T(n) = [mm]T(\lfloor\bruch{n}{2}\rfloor)[/mm] +
> [mm]T(\lceil\bruch{n}{2}\rceil)[/mm] +n   für n > 1
>  
> Da wir annehmen dürfen, dass n eine Zweierpotenz ist, also
> so aussieht n = [mm]2^{a}[/mm] , a [mm]\in \IN[/mm]
>  



Sorry, aber ich hatte bei meinem Tipp vergessen, dich auf Folgendes aufmerksam zu machen:

n=Zweierpotenz ist völlig unsinnig, wenn n die natürlichen Zahlen durchlaufen soll.

Wenn T nur für Zweierpotenzen definiert werden soll, müsste es heißen:

T(1)=0

[mm] T(2^n)=[/mm] [mm]T(\lfloor\bruch{2^n}{2}\rfloor)[/mm] + [mm]T(\lceil\bruch{2^n}{2}\rceil)[/mm] [mm] +2^n [/mm]
= [mm]T(2^{n-1})[/mm] + [mm]T(2^{n-1})[/mm] [mm] +2^n [/mm] = [mm]2*T(2^{n-1})[/mm]  [mm] +2^n. [/mm]


Man würde also immer nur 2-er-Potenzen addieren.
T(3), T(5),... wären gar nicht definiert, und das Ergebnis wäre auch trivial. Es wäre [mm]\lfloor\bruch{n}{2}\rfloor[/mm] = [mm]\lceil\bruch{n}{2}\rceil[/mm], die Unterscheidung damit sinnlos.


Nehmen wir an, es wäre doch so gemeint, wie es sich anhört. Wenn n eine Zweierpotenz wäre, wäre [mm] \bruch{n}{2} [/mm] ganzzahlig und damit [mm]\lfloor\bruch{n}{2}\rfloor[/mm] = [mm]\lceil\bruch{n}{2}\rceil[/mm], die Unterscheidung gäbe, wie in meinem obigen Gesagten, wieder keinen Sinn.

Was müsste man nun für n=7 rechnen? [mm]\lfloor\bruch{n}{2}\rfloor[/mm]=3, [mm]\lceil\bruch{n}{2}\rceil[/mm]=4, und dann 7 addieren? 7 ist aber keine 2-er-Potenz, n sollte aber eine sein!

Man merkt, dass die Bemerkung so unsinnig ist. Sie hätte heißen müssen:
Hinweis: Betrachten sie die 2-er-Potenzen, zwischen denen n liegt.
Dann wäre man auch sehr schnell auf die Funktion [mm] log_2 [/mm] gestoßen...

Bezug
                                
Bezug
Rekursionsgleichung lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:34 So 22.10.2017
Autor: pc_doctor

Danke für die Antwort.

Sofern ich weiß, soll davon ausgegangen werden, dass n eine Zweierpotenz ist. Nehmen wir an, als geschlossene Formel kommt [mm] log_2(n) [/mm] raus, dann wäre dieser Logarithmus für nicht-Zweierpotenzen nicht definiert, habe ich das richtig verstanden?

Bezug
                                        
Bezug
Rekursionsgleichung lösen: Korrigiert
Status: (Antwort) fertig Status 
Datum: 15:15 Mo 23.10.2017
Autor: HJKweseleit

Natürlich ist [mm] log_2(n) [/mm] für alle n definiert.

Ich schreibe mal auf, was ich für die von dir gebildete Reihe herausgefunden habe.

T(1) = 0 ( Rekursionsanker )
-------
T(2) = 2

T(3) = 5
T(4) = 8

T(5) = 12
T(6) = 16
T(7) = 20
T(8) = 24

T(9)  = 29
T(10) = 34
T(11) = 39
T(12) = 44
T(13) = 49
T(14) = 54
T(15) = 59
T(16) = 64

T(17) = 70

Die einzelnen Abschnitte bilden jeweils für sich eine arithmetische Folge und sind damit beschreibbar durch jeweils eine lineare Funktion der Form y=a*x+b, wobei a und b jeweils angepasst werden müssen. An den Nahtstellen kommt es zu überlappungen, die 8 kann man auch schon zur nächsten Reihe zählen, ebenso 24 und 64.

Man erhält so die Funktionen

y = 2x - 2      für x = 1   bis 2             mit [mm]\lfloor log_2(x) \rfloor[/mm]= 0
y = 3x - 4      für x von 2 bis 4 3           mit [mm]\lfloor log_2(x) \rfloor[/mm]= 1
y = 4x - 8      für x von 4 bis 8 7           mit [mm]\lfloor log_2(x) \rfloor[/mm]= 2
y = 5x - 16     für x von 8 bis 16 15         mit [mm]\lfloor log_2(x) \rfloor[/mm]= 3
y = 6x - 32     für x von 16 bis 32 31        mit [mm]\lfloor log_2(x) \rfloor[/mm]= 4
usw.

Allgemein erkennt man: Der Faktor a ist [mm]\lfloor log_2(x) \rfloor[/mm]  + 2, der Summand b ist [mm]-2^{\lfloor log_2(x) \rfloor+1}[/mm],

Somit [mm]T(n)=(\lfloor log_2(n) \rfloor \red{+} 2)*x - 2^{\lfloor log_2(x) \rfloor+1 [/mm]

Viel Spass beim Beweis durch vollständige Induktion ...


Bezug
                                                
Bezug
Rekursionsgleichung lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:59 Mo 23.10.2017
Autor: pc_doctor

Hallo nochmal,

vielen Dank für die Antwort.

Oh man, das kann ja mal was werden mit der Induktion. Ich versuche es :)

Bezug
                                                        
Bezug
Rekursionsgleichung lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:39 Mo 23.10.2017
Autor: HJKweseleit

Sorry, habe noch einen Schreibfehler gehabt und ihn nun mit rot korrigiert.

Bezug
                
Bezug
Rekursionsgleichung lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:04 Do 26.10.2017
Autor: vancouver

Hallo,
darf ich fragen wie du auf $ [mm] \lfloor log_2(n)\rfloor [/mm] $ gekommen bist?
LG

Bezug
                        
Bezug
Rekursionsgleichung lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 21:29 Do 26.10.2017
Autor: HJKweseleit

Der Wechsel bei den Abständen der Folgeglieder geschieht immer an einer Zweierpotenz, also bei n = 2, 4, 8, 16,...
Somit brauche ich die Information, zu welchem Abschnitt z.B. die 10 gehört. [mm] 2^3\le 10<2^4. [/mm] somit muss mir die 10 irgendwie den Exponenten 3 liefern, und alle Zahlen zwischen 8 und 15 ebenfalls.

Der [mm] log_2(n) [/mm] fragt: [mm] 2^{wieviel}=n, [/mm] und so kommt für die Zahlen von 8 bis 15 der Wert 3,... heraus, den ich dann abrunde.

Den [mm] log_2 [/mm] von x bekommst du, indem du einen beliebigen log (z.B. ln oder lg=log_10) nimmst und den Wert durch log(2) dividierst, wobei log(2) mit dem selben log genommen werden muss. Also:

[mm] log_2(x)=\bruch{ln(x)}{ln(2)}=\bruch{lg(x)}{lg(2)}=\bruch{log_5(x)}{log_5(2)}=... [/mm]

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Analysis des R1"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


Alle Foren
Status 6h 25m ago 3. Gonozal_IX
SIntRech/Stammfunktion/Integralfunktion
Status 7h 11m ago 2. matux MR Agent
OpRe/Reihenfolgeproblem
Status 9h 23m ago 56. HJKweseleit
MSons/Kann man beim Roulette verlier
Status 9h 29m ago 4. Son
MaßTheo/Metrischer Raum, Offene Mengen
Status 13h 38m ago 4. M.Rex
UDiskrMath/Türme von Hanoi (4Stäbe)
^ Seitenanfang ^
www.mathspace.org
[ Home | Forum | Knowledge | Courses | Members | Team | Contact ]