La [tex]P(x)[/tex] være et gitt ikkekonstant polynom med heltallige koeffisienter og la [tex]S[/tex] være et heltall. Vis at det finnes et heltall [tex]n[/tex] slik at [tex]P(n)[/tex] 'starter med' [tex]S[/tex].
(I den forstand at, dersom [tex]S[/tex] har [tex]r[/tex] sifre vil tallet dannet av de første [tex]r[/tex] sifrene i [tex]P(n)[/tex] (fra venstre og i riktig rekkefølge) være lik [tex]S[/tex].)
EDIT: Glemte å nevne at polynomet helst skulle være ikkekonstant.
Polynomer
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Jeg antar det er snakk om en positiv [tex]S[/tex] og et polynom med positiv ledende koeffisient (eventuelt at begge er negative, men i så fall kan man enkelt forandre beviset ved transformasjonen [tex]S \to -S[/tex], og [tex]P(x) \to -P(x)[/tex]). Hvis de har forskjellig fortegn er det lett å finne et moteksempel, f.eks [tex]S=1[/tex], og [tex]P(x)=-x^2[/tex].
Anta at [tex]P[/tex] har grad [tex]t \geq 1[/tex].
For at [tex]P(n)[/tex] skal begynne med [tex]S[/tex], må [tex]P(n) = 10^RS+T[/tex], hvor [tex]T[/tex] er et tall under [tex]10^R[/tex] for et heltall [tex]R[/tex]. Dvs at vi vil finne en [tex]n[/tex] for èn [tex]R[/tex] slik at [tex]10^RS \leq P(n) <10^RS+10^R=10^R(S+1)[/tex], eller [tex]1 \leq 10^{-R}\frac{P(n)}{S}<1+\frac{1}{S}[/tex].
Anta at [tex]P(x) = \sum a_ix^i[/tex]. La [tex]m=a_tS^{-1}[/tex]. Vi finner en løsning på ulikheten
[tex]1 < mn^t10^{-R}<1+\frac{1}{S}[/tex]. Dette tilsvarer [tex]\frac{\log m}{\log 10}+\frac{t}{\log 10} \log n -\frac{1+S^{-1}}{\log 10} < R < \frac{\log m}{\log 10}+\frac{t}{\log 10} \log n[/tex].
La [tex]f(n)=\frac{\log m}{\log 10}+\frac{t}{\log 10} \log n[/tex], og [tex]M =\min (1, \frac{1+S^{-1}}{\log 10})[/tex]. Vi har at [tex]f(n)-f(n-1) < M[/tex], når [tex]\frac{t}{\log 10} \log \frac{n}{n-1} < M[/tex], eller [tex]n > \frac{1}{1-10^{-\frac{M}{t}}}[/tex]. La [tex]N = \lfloor \frac{1}{1-10^{-\frac{M}{t}}} \rfloor +1[/tex]. Det betyr at [tex]f(n)[/tex] aldri vil "hoppe over" et heltall [tex]R > f(N)[/tex], og differansen [tex]f(n)-f(n-1)[/tex] vil alltid være mindre enn [tex]\frac{1+S^{-1}}{\log 10}[/tex] for enhver [tex]n \geq N[/tex]. Det betyr at for enhver [tex]R > f(N)[/tex], vil det finnes en [tex]n \geq N[/tex] slik at [tex]\frac{\log m}{\log 10}+\frac{t}{\log 10} \log n -\frac{1+S^{-1}}{\log 10} < R < \frac{\log m}{\log 10}+\frac{t}{\log 10} \log n[/tex]... [tex](1)[/tex]
Vi har at [tex]P(n) \leq a_tn^t +\max(|a_i|) \sum^{t-1}_i n^{i} \leq a_tn^t +Cn^{t-1}[/tex], for [tex]C=t\max(|a_i|)[/tex]. Dessuten har vi at [tex]P(n) \geq a_tn^t -\max(|a_i|) | \sum^{t-1}_i n^{i} \geq a_tn^t-Cn^{t-1}[/tex].
[tex](1)[/tex] impliserer at [tex]a_tS^{-1}n^t10^{-R}=1+k[/tex] for en [tex]k[/tex] slik at [tex]0<k<S^{-1}[/tex] for en [tex]n \geq N[/tex], for enhver [tex]R > f(N)[/tex]. Men siden [tex]a_tS^{-1}n^t10^{-R}<1+S^{-1}[/tex], så er [tex]Cn^{t-1}10^{-R}<\frac{C(1+S^{-1})}{a_tS^{-1}n}[/tex]. Velger vi [tex]R[/tex] stor nok (minst større enn [tex]f(N)[/tex]), så vil ulikheten [tex]R < \frac{\log m}{\log 10}+\frac{t}{\log 10} \log n[/tex] tvinge [tex]n[/tex] til å vokse over enhver nedre grense avhengig av [tex]R[/tex]. Dette betyr at [tex]Cn^{t-1}10^{-R}<\frac{C(1+S^{-1})}{a_tS^{-1}n} < \epsilon[/tex] for enhver valgt [tex]\epsilon > 0[/tex] ved riktig valg av [tex]R[/tex], for den/de [tex]n[/tex] som passer. Velger vi nå [tex]\epsilon = \frac{1}{2}\min(k,S^{-1}-k)[/tex], kan vi finne en [tex]R[/tex], og dermed en [tex]n[/tex] slik at [tex]1<-\epsilon + a_tS^{-1}n^t10^{-R}< P(n)S^{-1}10^{-R}< a_tS^{-1}n^t10^{-R} + \epsilon < 1+S^{-1}[/tex], som var hva vi ville vise.
Det ble ganske langt og rotete... Tar forbehold om feil, ser gjennom det i morra. Vis gjerne din løsning.
Anta at [tex]P[/tex] har grad [tex]t \geq 1[/tex].
For at [tex]P(n)[/tex] skal begynne med [tex]S[/tex], må [tex]P(n) = 10^RS+T[/tex], hvor [tex]T[/tex] er et tall under [tex]10^R[/tex] for et heltall [tex]R[/tex]. Dvs at vi vil finne en [tex]n[/tex] for èn [tex]R[/tex] slik at [tex]10^RS \leq P(n) <10^RS+10^R=10^R(S+1)[/tex], eller [tex]1 \leq 10^{-R}\frac{P(n)}{S}<1+\frac{1}{S}[/tex].
Anta at [tex]P(x) = \sum a_ix^i[/tex]. La [tex]m=a_tS^{-1}[/tex]. Vi finner en løsning på ulikheten
[tex]1 < mn^t10^{-R}<1+\frac{1}{S}[/tex]. Dette tilsvarer [tex]\frac{\log m}{\log 10}+\frac{t}{\log 10} \log n -\frac{1+S^{-1}}{\log 10} < R < \frac{\log m}{\log 10}+\frac{t}{\log 10} \log n[/tex].
La [tex]f(n)=\frac{\log m}{\log 10}+\frac{t}{\log 10} \log n[/tex], og [tex]M =\min (1, \frac{1+S^{-1}}{\log 10})[/tex]. Vi har at [tex]f(n)-f(n-1) < M[/tex], når [tex]\frac{t}{\log 10} \log \frac{n}{n-1} < M[/tex], eller [tex]n > \frac{1}{1-10^{-\frac{M}{t}}}[/tex]. La [tex]N = \lfloor \frac{1}{1-10^{-\frac{M}{t}}} \rfloor +1[/tex]. Det betyr at [tex]f(n)[/tex] aldri vil "hoppe over" et heltall [tex]R > f(N)[/tex], og differansen [tex]f(n)-f(n-1)[/tex] vil alltid være mindre enn [tex]\frac{1+S^{-1}}{\log 10}[/tex] for enhver [tex]n \geq N[/tex]. Det betyr at for enhver [tex]R > f(N)[/tex], vil det finnes en [tex]n \geq N[/tex] slik at [tex]\frac{\log m}{\log 10}+\frac{t}{\log 10} \log n -\frac{1+S^{-1}}{\log 10} < R < \frac{\log m}{\log 10}+\frac{t}{\log 10} \log n[/tex]... [tex](1)[/tex]
Vi har at [tex]P(n) \leq a_tn^t +\max(|a_i|) \sum^{t-1}_i n^{i} \leq a_tn^t +Cn^{t-1}[/tex], for [tex]C=t\max(|a_i|)[/tex]. Dessuten har vi at [tex]P(n) \geq a_tn^t -\max(|a_i|) | \sum^{t-1}_i n^{i} \geq a_tn^t-Cn^{t-1}[/tex].
[tex](1)[/tex] impliserer at [tex]a_tS^{-1}n^t10^{-R}=1+k[/tex] for en [tex]k[/tex] slik at [tex]0<k<S^{-1}[/tex] for en [tex]n \geq N[/tex], for enhver [tex]R > f(N)[/tex]. Men siden [tex]a_tS^{-1}n^t10^{-R}<1+S^{-1}[/tex], så er [tex]Cn^{t-1}10^{-R}<\frac{C(1+S^{-1})}{a_tS^{-1}n}[/tex]. Velger vi [tex]R[/tex] stor nok (minst større enn [tex]f(N)[/tex]), så vil ulikheten [tex]R < \frac{\log m}{\log 10}+\frac{t}{\log 10} \log n[/tex] tvinge [tex]n[/tex] til å vokse over enhver nedre grense avhengig av [tex]R[/tex]. Dette betyr at [tex]Cn^{t-1}10^{-R}<\frac{C(1+S^{-1})}{a_tS^{-1}n} < \epsilon[/tex] for enhver valgt [tex]\epsilon > 0[/tex] ved riktig valg av [tex]R[/tex], for den/de [tex]n[/tex] som passer. Velger vi nå [tex]\epsilon = \frac{1}{2}\min(k,S^{-1}-k)[/tex], kan vi finne en [tex]R[/tex], og dermed en [tex]n[/tex] slik at [tex]1<-\epsilon + a_tS^{-1}n^t10^{-R}< P(n)S^{-1}10^{-R}< a_tS^{-1}n^t10^{-R} + \epsilon < 1+S^{-1}[/tex], som var hva vi ville vise.
Det ble ganske langt og rotete... Tar forbehold om feil, ser gjennom det i morra. Vis gjerne din løsning.