Problem OM 1.1.2

% Algebra, Induction, ArithmeticSequence, Polynomials, Tedious

\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{fancyhdr}
\usepackage{lastpage}
% \usepackage{polski}
\usepackage{graphicx}
\usepackage{float}
\usepackage{fontspec}
\usepackage{enumitem}
\usepackage[most]{tcolorbox}

\setmainfont{Linux Libertine O}
\newfontfamily\russianfont{Linux Libertine O}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]

\usepackage[left=2cm, top=2cm, right=2cm, bottom=1cm, includeheadfoot,
    headheight=50pt, a4paper]{geometry}

\newcommand{\Name}{Hostek}
\newcommand{\Email}{your.email@example.com}
\newcommand{\ProblemNumber}{I OM, etap 1, zadanie 2}

\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{\Name \\ \Email}
\fancyhead[C]{\ProblemNumber}
\fancyfoot[C]{\thepage/\pageref{LastPage}}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\begin{document}
\fontsize{14}{15}\selectfont

\section*{Problem Statement}

Dowieść, że suma sześcianów $n$ kolejnych wyrazów postępu
arytmetycznego jest podzielna przez sumę tych wyrazów.

\bigskip

\noindent\textbf{Solution:}

\boxed{\textbf{Sposób 1:} \quad \text{(algebraiczny)}}

Na początku przypomnijmy podstawowe wzorki: (dowód na końcu)

Wzór na sumę $n$ pierwszych liczb naturalnych:
\begin{equation}
    \label{rr1}
    \sigma_1 = \sum_{i=1}^{i=n}i = \frac{n(n+1)}{2}
\end{equation}

Wzór na sumę kwadratów $n$ pierwszych liczb naturalnych:
\begin{equation}
    \label{rr2}
    \sigma_2 = \sum_{i=1}^{i=n}i^2 = \frac{n(n+1)(2n+1)}{6}
\end{equation}

Wzór na sumę sześcianów $n$ pierwszych liczb naturalnych:
\begin{equation}
    \label{rr3}
    \sigma_3 = \sum_{i=1}^{i=n}i^3 = \left(\sum_{i=1}^{i=n}i\right) ^ 2 = \left(\frac{n(n+1)}{2}\right) ^ 2
\end{equation}

W zadaniu mamy pewien ciąg (postęp) arytmetyczny. Oznaczmy przez $r$ różnicę tego ciągu oraz przez $a$ pierwszy wyraz.

Wtedy mamy takie coś do udowodnienia:
$$ a + (a + r) + \ldots + (a + (n-1)r) \mid a^3 + (a + r)^3 + \ldots + (a + (n-1)r)^3$$

Lewa strona tego wyrażenia jest równa: $na + \frac{n(n-1)}{2}r$.

Skorzystajmy ze wzoru skróconego mnożenia by obliczyć prawą stronę:
\begin{equation}
    (a+b)^3 = a^3 + 3a^2b+3b^2a+b^3
\end{equation}

Czyli:
\begin{equation}
    (a+kr)^3 = a^3 + 3kra^2 + 3k^2r^2a + k^3r^3
\end{equation}

Po prawej stronie mamy iście:
\begin{align*}
\sum_{i=0}^{i = n - 1}\left(a + ir\right)^3 &= \sum_{i=0}^{i = n - 1}\left(a^3 + 3ira^2 + 3i^2r^2a + i^3r^3\right) \\ 
&= \sum_{i=0}^{i = n - 1}a^3 + \sum_{i=0}^{i = n - 1} 3ira^2 + \sum_{i=0}^{i = n - 1}3i^2r^2a + \sum_{i=0}^{i = n - 1}i^3r^3 \\ 
&= a^3\sum_{i=0}^{i = n - 1}(1) + 3ra^2\sum_{i=0}^{i = n - 1} (i) + 3r^2a\sum_{i=0}^{i = n - 1}(i^2) + r^3\sum_{i=0}^{i = n - 1}(i^3) \\ 
&= a^3n + 3ra^2\left(\frac{n(n-1)}{2}\right) + 3r^2a\left(\frac{(n-1)n(2n-1)}{6}\right) + r^3\left(\frac{n(n-1)}{2}\right)^2 
% &= a^3n + \frac{n(n-1)}{2}r\left(3a^2 + 3ra\left(\frac{(2n-1)}{3}\right) + r^2\left(\frac{n(n-1)}{2}\right)\right) \\ 
\end{align*}

Obliczając dalej:
\begin{align*}
\sum_{i=0}^{i = n - 1}\left(a + ir\right)^3 &= \left(na + \frac{n(n-1)}{2}r\right)a^2 - \frac{n(n-1)}{2}ra^2 + 3ra^2\left(\frac{n(n-1)}{2}\right) + \\ 
&+ 3r^2a\left(\frac{(n-1)n(2n-1)}{6}\right) + r^3\left(\frac{n(n-1)}{2}\right)^2 \\
&= \left(na + \frac{n(n-1)}{2}r\right)a^2 - \frac{n(n-1)}{2}ra^2 + ar(n-1)\left(na + \frac{n(n-1)}{2}r\right) + \\ 
&+ ra^2\left(\frac{n(n-1)}{2}\right) + r^2a\left(\frac{(n-1)n^2}{2}\right) + r^3\left(\frac{n(n-1)}{2}\right)^2 \\
 &= \left(na + \frac{n(n-1)}{2}r\right)a^2 + ar(n-1)\left(na + \frac{n(n-1)}{2}r\right) + \\ 
& + r^2a\left(\frac{(n-1)n^2}{2}\right) + r^3\left(\frac{n(n-1)}{2}\right)^2 \\
&= \left(na + \frac{n(n-1)}{2}r\right)a^2 + ar(n-1)\left(na + \frac{n(n-1)}{2}r\right) + \\ 
& + r^2a\left(\frac{(n-1)n^2}{2}\right) + r^3\left(\frac{n(n-1)}{2}\right)^2 \\
&= \left(na + \frac{n(n-1)}{2}r\right)a^2 + ar(n-1)\left(na + \frac{n(n-1)}{2}r\right) + \\ 
& + \left(na + \frac{n(n-1)}{2}r\right)\left(\frac{n(n-1)}{2}r^2\right) \\
&= \left(na + \frac{n(n-1)}{2}r\right)\left(a^2 + ar(n-1) + \frac{n(n-1)}{2}r^2\right) \\ 
\end{align*}

Jak widać, po przekształceniach równoważnych otrzymujemy, że suma sześcianów $n$ pierwszych wyrazów postępu arytmetycznego jest równa iloczynowi sumy $n$ pierwszych wyrazów tegoż postępu i jakiejś innej liczby całkowitej. 

Co oznacza, że suma sześcianów $n$ kolejnych wyrazów postępu
arytmetycznego jest podzielna przez sumę tych wyrazów.

Co należało dowieść.

\boxed{\textbf{Sposób 2:} \quad \text{(firmówka)}}

Będziemy nadal korzystać z równań \eqref{rr1}, \eqref{rr2}, \eqref{rr3}.

Zauważmy dodatkowo, że $\sigma_3 = \sigma_1 \cdot \frac{2n+1}{3}$.

Tak jak poprzednio oznaczamy przez $a$ pierwszy wyraz naszego postępu i przez $r$ jego różnicę.

Oznaczmy przez $T$ sumę sześcianów $n$ pierwszych wyrazów postępu arytmetycznego, a przez $S$ sumę $n$ pierwszych wyrazów tegoż postępu.

Otrzymujemy tak jak poprzednio:
\begin{equation}
    \label{rr4}
    S = na + \sigma_1 r
\end{equation}

Oraz to:
\begin{align*}
    T&= a^3 + (a+r)^3 + \ldots + \left(a + \left(n-1\right)r\right)^3\\
    &= na^3 + 3\cdot(1+\ldots+(n-1))a^2r + 3\cdot(1^2+\ldots+(n-1)^2)ar^2+\\
    &+(1^3+\ldots+(n-1)^3)r^3 \\
    &= na^3 + 3\sigma_1a^2r+3\sigma_2ar^2+\sigma_3r^3\\
    &= na^3 + 3\sigma_1a^2r+(2n-1)\sigma_1ar^2+\sigma_1^2r^3
\end{align*}

Czyli oznaczmy to nasze końcowe równanko:
\begin{equation}
    \label{rr5}
    T = na^3 + 3\sigma_1a^2r+(2n-1)\sigma_1ar^2+\sigma_1^2r^3
\end{equation}

Sumy $S$ i $T$, wyrażone odpowiednio wzorami \eqref{rr4} i \eqref{rr5}, są wielomianami
uporządkowanymi względem $a$. Najwyższe ich wyrazy $na^3$ i $na$
dają iloraz $a^2$
, a najniższe wyrazy, czyli $\sigma_1^2r^3$ i $\sigma_1 r$, dają iloraz
$\sigma_1r^2$.

Czyli, jeśli wielomian $T$ jest podzielny przez dwumian $S$, to iloraz ma postać:
$$\frac{T}{S} = a^2 + xar + \sigma_1r^2$$

Więc, chcemy to sprawdzić... Otóż:
\begin{align*}
S(a^2 + xar + \sigma_1r^2) &= (na + \sigma_1 r)(a^2 + xar + \sigma_1r^2) \ \\
&= na^3 + (nx+\sigma_1)a^2r+(x+n)\sigma_1ar^2+\sigma_1^2r^3 \\
\end{align*}

Jeśli weźmiemy $x=n-1$ to otrzymamy to samo co w \eqref{rr5}!

A zatem możemy powiedzieć, że:
$$ T = S(a^2 + (n-1)ar + \sigma_1r^2)$$

Co należało dowieść.

Sposób trzeci na następnej stronie.

\clearpage

\boxed{\textbf{Sposób 3:} \quad \text{(indukcja)}}

\subsection*{Dowód indukcyjny}

\textbf{Teza:} Dla każdego \( n \in \mathbb{N} \):
\[
\sum_{i=0}^{n-1} (a + ir)^3 = \left(na + \frac{n(n-1)}{2}r \right) \left(a^2 + ar(n-1) + \frac{n(n-1)}{2}r^2 \right)
\]

\textbf{Podstawa indukcji (\( n = 1 \)):}
\[
\sum_{i=0}^{0} (a + 0 \cdot r)^3 = a^3
\]
Prawa strona:
\[
\left(1 \cdot a + \frac{1 \cdot 0}{2}r \right) \left(a^2 + a \cdot r \cdot 0 + \frac{1 \cdot 0}{2}r^2 \right) = a \cdot a^2 = a^3
\]
Podstawa zachodzi.

\textbf{Założenie indukcyjne:} Dla \( n = k \):
\[
\sum_{i=0}^{k-1} (a + ir)^3 = \left(ka + \frac{k(k-1)}{2}r \right) \left(a^2 + ar(k-1) + \frac{k(k-1)}{2}r^2 \right)
\]

\textbf{Krok indukcyjny (\( n = k + 1 \)):}
Rozważmy:
\[
\sum_{i=0}^{k} (a + ir)^3 = \underbrace{\sum_{i=0}^{k-1} (a + ir)^3}_{\text{Założenie}} + (a + kr)^3
\]
Podstawiając założenie:
\[
= \left(ka + \frac{k(k-1)}{2}r \right) \left(a^2 + ar(k-1) + \frac{k(k-1)}{2}r^2 \right) + (a + kr)^3
\]

\vspace{5mm}
\textbf{Krok 1: Rozwiń \( (a + kr)^3 \):}
\[
(a + kr)^3 = a^3 + 3a^2(kr) + 3a(kr)^2 + (kr)^3 = a^3 + 3k a^2 r + 3k^2 a r^2 + k^3 r^3
\]

\vspace{5mm}
\textbf{Krok 2: Wymnóż nawiasy z założenia indukcyjnego:}
\[
\left(ka + \frac{k(k-1)}{2}r \right) \cdot \left(a^2 + ar(k-1) + \frac{k(k-1)}{2}r^2 \right)
\]
Wymnóż każdy składnik:

\begin{align*}
& ka \cdot a^2 & = k a^3 \\
& ka \cdot ar(k-1) & = k(k-1) a^2 r \\
& ka \cdot \frac{k(k-1)}{2} r^2 & = \frac{k^2(k-1)}{2} a r^2 \\
& \frac{k(k-1)}{2} r \cdot a^2 & = \frac{k(k-1)}{2} a^2 r \\
& \frac{k(k-1)}{2} r \cdot ar(k-1) & = \frac{k(k-1)^2}{2} a r^2 \\
& \frac{k(k-1)}{2} r \cdot \frac{k(k-1)}{2} r^2 & = \frac{k^2(k-1)^2}{4} r^3
\end{align*}

Sumując wszystkie składniki:
\[
k a^3 + \left(k(k-1) + \frac{k(k-1)}{2}\right) a^2 r + \left(\frac{k^2(k-1)}{2} + \frac{k(k-1)^2}{2}\right) a r^2 + \frac{k^2(k-1)^2}{4} r^3
\]

\vspace{5mm}
\textbf{Krok 3: Uprość współczynniki:}

1. Dla \( a^2 r \):
\[
k(k-1) + \frac{k(k-1)}{2} = \frac{2k(k-1) + k(k-1)}{2} = \frac{3k(k-1)}{2}
\]

2. Dla \( a r^2 \):
\[
\frac{k^2(k-1) + k(k-1)^2}{2} = \frac{k(k-1)(k + (k-1))}{2} = \frac{k(k-1)(2k - 1)}{2}
\]

3. Dla \( r^3 \):
\[
\frac{k^2(k-1)^2}{4}
\]

\vspace{5mm}
\textbf{Krok 4: Zsumuj z \( (a + kr)^3 \):}
\[
\begin{aligned}
& k a^3 + \frac{3k(k-1)}{2} a^2 r + \frac{k(k-1)(2k - 1)}{2} a r^2 + \frac{k^2(k-1)^2}{4} r^3 \\
& + \ a^3 + 3k a^2 r + 3k^2 a r^2 + k^3 r^3 
\end{aligned}
\]

Grupuj wyrazy podobne:
\[
\begin{aligned}
& (k a^3 + a^3) + \left(\frac{3k(k-1)}{2} a^2 r + 3k a^2 r \right) \\
& + \left(\frac{k(k-1)(2k - 1)}{2} a r^2 + 3k^2 a r^2 \right) + \left(\frac{k^2(k-1)^2}{4} r^3 + k^3 r^3 \right)
\end{aligned}
\]

\vspace{5mm}
\textbf{Krok 5: Uprość każdą grupę:}

1. \( a^3 \):
\[
(k + 1) a^3
\]

2. \( a^2 r \):
\[
\frac{3k(k-1)}{2} + 3k = \frac{3k(k-1) + 6k}{2} = \frac{3k(k + 1)}{2}
\]

3. \( a r^2 \):
\[
\frac{k(k-1)(2k - 1)}{2} + 3k^2 = \frac{2k^3 - k^2 - 2k^2 + k + 6k^2}{2} = \frac{2k^3 + 3k^2 + k}{2} = \frac{k(2k^2 + 3k + 1)}{2}
\]

4. \( r^3 \):
\[
\frac{k^2(k-1)^2}{4} + k^3 = \frac{k^2(k^2 - 2k + 1) + 4k^3}{4} = \frac{k^4 + 2k^3 + k^2}{4} = \frac{k^2(k + 1)^2}{4}
\]

\vspace{5mm}
\textbf{Krok 6: Zbuduj prawą stronę dla \( n = k + 1 \):}
\[
\left((k+1)a + \frac{(k+1)k}{2}r \right) \left(a^2 + ar k + \frac{(k+1)k}{2}r^2 \right)
\]

Wymnóż nawiasy:
\[
\begin{aligned}
& (k+1)a \cdot a^2 = (k+1)a^3 \\
& (k+1)a \cdot ar k = k(k+1)a^2 r \\
& (k+1)a \cdot \frac{(k+1)k}{2} r^2 = \frac{(k+1)^2 k}{2} a r^2 \\
& \frac{(k+1)k}{2} r \cdot a^2 = \frac{k(k+1)}{2} a^2 r \\
& \frac{(k+1)k}{2} r \cdot ar k = \frac{k^2(k+1)}{2} a r^2 \\
& \frac{(k+1)k}{2} r \cdot \frac{(k+1)k}{2} r^2 = \frac{k^2(k+1)^2}{4} r^3
\end{aligned}
\]

Sumując wszystkie składniki:
\[
(k+1)a^3 + \left(k(k+1) + \frac{k(k+1)}{2}\right)a^2 r + \left(\frac{(k+1)^2 k}{2} + \frac{k^2(k+1)}{2}\right)a r^2 + \frac{k^2(k+1)^2}{4} r^3
\]

\vspace{5mm}
\textbf{Krok 7: Porównaj obie strony:}
Wszystkie współczynniki \( a^3 \), \( a^2 r \), \( a r^2 \), \( r^3 \) po obu stronach są identyczne. Na przykład dla \( a^2 r \):
\[
\frac{3k(k+1)}{2} \quad \text{(lewa)} \quad \text{vs} \quad \frac{3k(k+1)}{2} \quad \text{(prawa)}
\]
Analogicznie dla pozostałych. Zatem równość zachodzi dla \( n = k + 1 \).

\vspace{5mm}
\textbf{Wniosek:} Na mocy zasady indukcji matematycznej, równość jest prawdziwa dla wszystkich \( n \in \mathbb{N} \).

Czyli udało nam się dowieść, że suma sześcianów $n$ pierwszych wyrazów postępu arytmetycznego jest równa iloczynowi sumy $n$ pierwszych wyrazów tegoż postępu i jakiejś innej liczby całkowitej. 

Co oznacza, że suma sześcianów $n$ kolejnych wyrazów postępu
arytmetycznego jest podzielna przez sumę tych wyrazów.

Co należało dowieść.

\end{document}