Analysis/Cauchy sequences, cauchy criterion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8e5be64d",
   "metadata": {},
   "source": [
    "#### Cauchy sequence\n",
    "\n",
    "$ \\forall \\epsilon > 0, \\exists K \\in \\mathbb{N}, \\forall k, m \\ge K: ||x_k - x_m || < \\epsilon $\n",
    "\n",
    "My intepretation is that after a certain point in the sequence, the difference of any two elements is within $ \\epsilon $.\n",
    "\n",
    "---\n",
    "\n",
    "#### Cauchy Criterion\n",
    "\n",
    "This is powerful because you can prove convergence without having to guess what the limit is.\n",
    "\n",
    "The theorem states:\n",
    "\n",
    "In $ R^n $, a sequence converges _iff_ it is a Cauchy Sequence.\n",
    "\n",
    "$ (\\Rightarrow) $\n",
    "\n",
    "$ \\forall \\epsilon > 0, \\exists K(\\epsilon) \\in \\mathbb{N}, \\forall k \\ge K(\\epsilon) : |x_k - \\bar x| < \\epsilon $\n",
    "\n",
    "Fix: $ || x_k - \\bar x || < \\frac{\\epsilon}{2}, \\forall k \\ge K(\\epsilon) $\n",
    "\n",
    "Consider:\n",
    "\n",
    "$ || x_m - x_k || = || x_m - \\bar x + \\bar x - x_k || $\n",
    "\n",
    "$ || x_m - x_k || \\le || x_m - \\bar x || + || \\bar x - x_k || < \\epsilon,\\space\\space\\space\\space \\forall k, m \\ge K(\\epsilon) $\n",
    "\n",
    "Notice that this doesn't say anything about the distance from $ x_m $ to $ \\bar x $, but it doesn't need to, since if $ k $ is the lowest possible index such that $\\forall k \\ge K(\\epsilon)$, then $ m $ is at least a larger index. \n",
    "\n",
    "Then:\n",
    "\n",
    "$ || x_m - x_k || < \\epsilon $\n",
    "\n",
    "$ (\\Leftarrow) $\n",
    "\n",
    "![Cauchy Criterion](Screenshot_2023-07-30_12-16-03.png)\n",
    "\n",
    "#### Example - use Cauchy Criterion to prove convergence\n",
    "\n",
    "Consider:\n",
    "\n",
    "$ \\{x_k\\} = \\frac{\\cos 2}{2} + \\frac{\\cos 2(2)}{2^2} + \\frac{\\cos 2(3)}{2^3} + ... $\n",
    "\n",
    "$ \\{x_k\\} = \\sum_k=1 \\frac{\\cos 2k}{2^k} $\n",
    "\n",
    "Then does it converge? The numerator is cyclical, but the denominator is increasing. It does seem to converge.\n",
    "\n",
    "Because the numerator oscillates then it is hard to guess what the limit is.\n",
    "\n",
    "We can instead use Cauchy Criterion.\n",
    "\n",
    "First let's convince ourselves that it's true:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a69d36a8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjAAAAGkCAIAAACgjIjwAAAQo0lEQVR42u3dT2hc9drA8d8ELUkWKRUvFQtC0byDcLscAl0Zg6sScDHEXUGbTW/p4tpevXRREqgJxeoqJQWlulGaOlLBF4QUspBZDCMkGzehUlTcBGIVAoaAbe5iXkLettcm8yfnOZPPZ5WcZJInh+P5ev5NC5ubmwkAstaT9QAAkJIgARCEIAEQgiABEIIgARCCIAEQgiABEIIgARCCIAEQgiABEIIgARCCIAEQgiABEIIgARCCIAEQgiABEIIgARCCIAEQgiABEIIgARCCIAEQgiABEIIgARCCIAEQgiABEIIgARCCIAEQQp6CNDU1VS6XT506de/evcaS+/fvnz9/vlwuj46Ofvfdd1kPCEDzchOker2+srJSqVTK5fLMzExj4e3bt/v7+yuVypUrVyYnJ7OeEYDm5SZIS0tLIyMjKaXh4eF6vd5YeOTIkZMnT6aUDh8+fODAgaxnBKB5T2U9wE6trq4Wi8WUUm9v7/r6emPhsWPHUkp37tyZmJg4e/bs9u9vfDMAW5aXl7Me4a/kJkgDAwNra2sppY2Njb6+vq3l165dq9VqExMTg4ODD70k+KrPhWKxaDW2yDpsC6uxdfH/Nz03p+xKpVK1Wk0pVavVUqnUWDg/P3/37t3r168/WiMA8iU3R0hDQ0MLCwvj4+OFQmF6enpxcfHy5cuDg4O1Wu3EiRMppUOHDn3++edZjwlAk3ITpEKhcOHCha1Pn3322bm5uayHAqBtcnPKjkw4a98667AtrMb9QJAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQ4iqcW8h6BIC9I0ihaRKwfwgSACEIEgAhCBIAIQhSaJsfvOoyErBPCBIAIQgSACEIUlCFcwubH7ya9RQAe0eQonMZCdgnBAmAEPIUpKmpqXK5fOrUqXv37m1fPjc39/XXX2c9HQAtyU2Q6vX6yspKpVIpl8szMzONhQ8ePDh9+vSlS5eyng6AVj2V9QA7tbS0NDIyklIaHh6+evVqY2FPT8/s7Ozs7OxjX1IsFrc+Xl5ezvovaF7jMpJ7HIDd2r4bjC83QVpdXW2s2d7e3vX19Z28JNcRAmjd9t1g/Djl5pTdwMDA2tpaSmljY6Ovry/rcQBos9wEqVQqVavVlFK1Wi2VSlmPA0Cb5SZIQ0NDBw8eHB8fv3HjxpkzZxYXF994442sh+qUR68YeRoJ6Hq5uYZUKBQuXLiw9emzzz47NzfX+Pj06dNZTwdAq3JzhARAdxMkAEIQpNxwGQnoboIEQAiCBEAIggRACIKUJy4jAV1MkMLxPqrA/iRIAIQgSACEIEg54zIS0K0ECYAQBAmAEAQJgBAEKX9cRgK6kiABEIIgxeKpWGDfEiQAQhCkXHIZCeg+ggRACIIEQAiCBEAIgpRXLiMBXUaQAAhBkAAIQZAC8VQssJ8JUo65jAR0E0ECIARBAiAEQQIgBEECIARByjf3NQBdQ5AACEGQAAhBkKLwVCywzwlS7rmMBHQHQQIgBEECIARBAiAEQeoGLiMBXUCQAAhBkAAIQZAACEGQQmj9qViXkYC8EyQAQhAkAEIQJABCEKTu4TISkGuCBEAIggRACIIEQAiC1FVcRgLyS5Cy59+KBUiCBEAQT2U9AN1s6/yhQ0DgiRwhdZtol5E2P3i1MVKoqYCAHCHRKduvjTU+cMAE/AVBoiMee6fG1pJGmWQJ2E6QaL8n3jfogAl4lCB1ocY1m6z28jv/1Q8dMCVlgv0t90GamppaXFw8ePDg+++//8wzz2Q9Ds1wKg9IeQ9SvV5fWVmpVCrffPPNzMzMxYsXs55o17rsqdgW/xyn8mA/y3eQlpaWRkZGUkrDw8NXr17Nepz9rl1xffRUXsoiTq3cpy6l0IR8B2l1dbVYLKaUent719fXH/pq40sNy8vLWQ+7p/b+MlInft32H/hoHtr769r78z10RUD/k/UAT5TvIA0MDKytraWUNjY2+vr6HvrqfotQhvYgfo/+/Mfu9Hc4Rqfz5giJgIr/m/UET5LvIJVKpVu3bo2Ojlar1VKplPU47KnH7vR3eGgiGBBQvoM0NDS0sLAwPj5eKBSmp6ezHmefCnVfRpxJgN3Kd5AKhcKFCxeyniKovbmMFKpGQK55c1Wap0ZAGwkSTVIjoL0EKUud3qf7dx+AHMn3NSSeaPt7H7Qxfg6PgLYTpH2hvVlSI6ATBGkfaUuW1AjoEEHad1rJkhoBneOmhn1q84NXG7c8ZD0IwP8RpH1tV7fhOTwCOsopu/1uh2fw1AjoNEEipSdlSY2APSBImQm4l39slgLOCXQlQeJhHXqWFuCvCRKPt5UlTQL2hrvs+CtqBOwZQQIgBEECIARBAiAEQQIgBEECIARByobbqQEeIkgAhCBIAIQgSACEIEgAhCBIAIQgSACEIEgAhCBIAIQgSBnwVCzAowQJgBAECYAQBAmAEAQJgBAECYAQBAmAEAQJgBAECYAQBGmveSoW4LEECYAQBAmAEAQJgBAECYAQBAmAEAQJgBAECYAQBGlPeQgJ4L8RJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhCkveOpWIC/IEgAhCBIAIQgSACEIEgAhCBIAISQpyBNTU2Vy+VTp07du3dv+/K5ubmvv/466+kAaEluglSv11dWViqVSrlcnpmZaSx88ODB6dOnL126lPV0ALTqqawH2KmlpaWRkZGU0vDw8NWrVxsLe3p6ZmdnZ2dnH/uSYrG49fHy8nLWfwHAXtu+G4wvN0FaXV1trNne3t719fWdvCRUhDwVC+y97bvB+HGKHqSbN28uLCwcPXp0YGBgbW0tpbSxsdHX15f1XAC0WfQgjY2NjY2NpZRqtdqtW7dGR0er1WqpVMp6LgDaLDc3NQwNDR08eHB8fPzGjRtnzpxZXFx84403sh4KgLYpbG5uZj1DRxSLRdeQALZE2ys+KjdHSAB0N0ECIARBAiAEQQIgBEHaC+5oAHgiQQIgBEECIARBAiAEQQIgBEECIARBAiAEQQIgBEECIARB6jhPxQLshCABEIIgARCCIAEQgiABEIIgARCCIAEQgiABEIIgARCCIHWWp2IBdkiQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZA6yFOxADsnSACEIEgAhCBIAIQgSACEIEgAhCBIAIQgSACEIEid4iEkgF0RpI5QI4DdEqT2UyOAJggSACEIUps5PAJojiC1kxoBNE2QAAhBkNrG4RFAKwSpPdQIoEWC1AZqBNA6QQIgBEFqlcMjgLYQpJaoEUC7CBIAIQhS8xweAbSRIDVJjQDaS5CaoUYAbSdIAIQgSLvm8AigEwRpd9QIoEMECYAQ8hSkqampcrl86tSpe/fuNZbcv3///Pnz5XJ5dHT0u+++6/QADo8AOic3QarX6ysrK5VKpVwuz8zMNBbevn27v7+/UqlcuXJlcnKyowOoEUBH5SZIS0tLIyMjKaXh4eF6vd5YeOTIkZMnT6aUDh8+fODAgaxnBKB5T2U9wE6trq4Wi8WUUm9v7/r6emPhsWPHUkp37tyZmJg4e/bsQy9pfH/D8vJyK7/d4RGQR9t3g/FFD9LNmzcXFhaOHj06MDCwtraWUtrY2Ojr69v6hmvXrtVqtYmJicHBwYde22KEtqgRkFPbd4Px4xQ9SGNjY2NjYymlWq1269at0dHRarVaKpUaX52fn7979+7169d7ejp17lGNAPZG9CBtGRoaWlhYGB8fLxQK09PTi4uLly9fHhwcrNVqJ06cSCkdOnTo888/z3pMAJpU2NzczHqGjigWi62fsnN4BHSNtuwVOyo3d9ntPTUC2EuC9F+pEcBeEiQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECQAQhAkAEIQJABCECT+SrFYzHqE3LMO28Jq3A8ECYAQnsp6gF2YmppaXFw8ePDg+++//8wzz6SU/vjjj3Pnzv32229//vnn5cuXX3zxxaxnBKBJuTlCqtfrKysrlUqlXC7PzMw0Fn711Vcvv/zyjRs33nrrrY8//jjrGQFoXm6OkJaWlkZGRlJKw8PDV69ebSx85ZVX+vv719bWfvjhh+eee+6hlzjp3BZWY+usw7awGrteboK0urra2Bx7e3vX19cbC59//vmU0ttvv12r1T766KPt37+8vJz1yADsQvQg3bx5c2Fh4ejRowMDA2traymljY2Nvr6+xldXVlYOHTr04Ycf/vTTT+fPn//iiy+ynheAJkW/hjQ2Nnbt2rV33323VCpVq9WUUrVaLZVKja9ev379yy+/TCmtra0VCoWshwWgeYXNzc2sZ9iRzc3N6enpu3fvFgqF6enpn3/++fLlyzMzM//85z//+OOPQqEwOTn597//PesxAWhSboIEQHeLfsoOgH1CkAAIQZAACCH6bd/NefRNhtitP//8s1Qq/e1vf0spvfbaa//617+ynih/5ubm+vv7R0dHk22yWVvr0AbZnPv377/77rs//vjjxsbGxYsXS6VS5E2xC4+QHvsmQ+zWL7/8Mjw8PD8/Pz8/7z/+3Xrw4MHp06cvXbrU+NQ22YSH1qENsjm3b9/u7++vVCpXrlyZnJwMvil2YZC2v8lQvV7Pepy8+umnn37//fdz585NTk7++uuvWY+TMz09PbOzs//4xz8an9omm/DQOrRBNufIkSMnT55MKR0+fPjAgQPBN8UuDNLq6urAwED6/28yxG49/fTTx48fv3jx4vPPP//vf/8763HyzTbZOhtkc44dO/bSSy/duXPnzJkzZ8+eDb4pduE1pMe+yRC7dfz48ePHj6eU3nzzzU8//TTrcfLNNtk6G2TTrl27VqvVJiYmBgcHv//++8ibYhceIT32TYbYrU8++eTGjRsppe+///6FF17Iepx8s022zgbZnPn5+bt3716/fn1wcDCF3xS78AhpaGhoYWFhfHy88SZDWY+TV6+//vo777zz5Zdf9vT0vPfee1mPk2+2ydbZIJvz7bff1mq1EydOpJQOHTr02WefRd4UvXUQACF04Sk7APJIkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACEGQAAhBkAAIQZAACOE/mAsUz4n/XtIAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "k = 1:20;\n",
    "x_k = cos(2.*k)./2.^k;\n",
    "\n",
    "plot(k, x_k);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a212d48",
   "metadata": {},
   "source": [
    "This is convincing, that there will be some $ \\epsilon $ such that $ K(\\epsilon) > 0 $ will be sufficiently large that $ k, m > K(\\epsilon) $ are the indices of elements $ x_k, x_m $ where the Euclidean distance between those will always be $ < \\epsilon $.\n",
    "\n",
    "So first, choose $ \\epsilon $\n",
    "\n",
    "Let's fix $ || x_k - x_m || < \\frac{\\epsilon}{2} $\n",
    "\n",
    "We can use the triangle inequality:\n",
    "\n",
    "$ || x_k - x_m || \\le || x_k || + || x_m || $\n",
    "\n",
    "And because of the choice for $ \\epsilon $:\n",
    "\n",
    "$ || x_k - x_m || \\le || x_k || + || x_m || < \\epsilon $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "6160070f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Symbolic pkg v3.0.1: Python communication link active, SymPy v1.4.\n",
      "ans = (sym)\n",
      "\n",
      "     ⎛ x⎞\n",
      "  log⎝2 ⎠\n",
      "  ───────\n",
      "   log(2)\n",
      "\n"
     ]
    }
   ],
   "source": [
    "pkg load symbolic;\n",
    "syms x;\n",
    "log2(2^x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5a90923",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Octave",
   "language": "octave",
   "name": "octave"
  },
  "language_info": {
   "file_extension": ".m",
   "help_links": [
    {
     "text": "GNU Octave",
     "url": "https://www.gnu.org/software/octave/support.html"
    },
    {
     "text": "Octave Kernel",
     "url": "https://github.com/Calysto/octave_kernel"
    },
    {
     "text": "MetaKernel Magics",
     "url": "https://metakernel.readthedocs.io/en/latest/source/README.html"
    }
   ],
   "mimetype": "text/x-octave",
   "name": "octave",
   "version": "6.4.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}