Diskret matematik · 2024-11-20

Uppgift 1

Uppgift 1

Lös följande problem.

(a)

Bestäm det minsta positiva heltalet $A$, som gör att den Diofantiska ekvationen $ Ax - 143y = 1 $ inte går att lösa.

(b)

Avgör om påståendet nedan är sant eller inte: \[ \forall y \in \setR \; \exists x \in \setR \; : \; x^3+y^2x-y + 100000=0. \]

(c)

Om man ska visa identiteten $\displaystyle \sum_{k=0}^n (k+1)\cdot 2^k = 1+n\cdot 2^{n+1}$ för $n \geq 0$ med induktion behövs ett basfall. Vad är basfallet? Om formeln ovan för ett visst $n$ är induktionsantagandet, vilket påstående vill man därefter visa?

Visa lösningDölj lösning

Vi har att $143 = 11 \cdot 13$, och ekvationen saknar lösning om $\SGD(A,11\cdot 13) \neq 1$. Detta sker om $A = 11$, men inte för något mindre $A$.
För varje värde på $y$, så får vi en tredjegradsekvation med reella koefficienter. Sådana tredjegradare har alltid en reell rot, $x$, så påståendet är sant.
Basfallet är att verifiera identiteten för $n=0$, dvs. att $(0+1)\cdot 2^{0} = 1+0\cdot 2^{0+1}$. Om formeln ovan är induktionsantagandet, så måste vi visa formeln för nästa värde på $n$, så vi vill visa att \[ \sum_{k=0}^{n+1} (k+1)\cdot 2^k = 1+(n+1)\cdot 2^{n+2}. \]