sum_of_cosines.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:776b06a1a1c28ec99e58a7ab15a07acdf66ec7e208c0048f7fe2c711ba0f9fc0"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Sum of sines and cosines"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "See: [arithmetic progression of cosines paper](http://evergreen.loyola.edu/mpknapp/www/papers/knapp-sv.pdf)."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Theorems:\n",
      "    \n",
      "$$\n",
      "\\sum_{n=0}^{N-1} \\cos(a + nd) = \\frac{\\sin(Nd / 2)}{\\sin(d / 2)}\n",
      "                              \\cos \\bigg ( a + \\frac{(N - 1) d}{2} \\bigg ) \\; \\mathrm{for} \\; \\sin(d / 2) \\ne 0 \\\\\n",
      "\\sum_{n=0}^{N-1} \\sin(a + nd) = \\frac{\\sin(Nd / 2)}{\\sin(d / 2)}\n",
      "                              \\sin \\bigg ( a + \\frac{(N - 1) d}{2} \\bigg ) \\; \\mathrm{for} \\; \\sin(d / 2) \\ne 0\n",
      "$$                                    "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Is this numerically the case?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from __future__ import print_function, division"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np\n",
      "\n",
      "def predicted_cos_sum(a, d, n):\n",
      "    d2 = d / 2.\n",
      "    return np.sin(n * d2) / np.sin(d2) * np.cos(a + (n - 1) * d / 2)\n",
      "\n",
      "def predicted_sin_sum(a, d, n):\n",
      "    d2 = d / 2.\n",
      "    return np.sin(n * d2) / np.sin(d2) * np.sin(a + (n - 1) * d / 2)\n",
      "\n",
      "def actual_cos_sum(a, d, n):\n",
      "    angles = np.arange(n) * d + a\n",
      "    return np.sum(np.cos(angles))\n",
      "\n",
      "def actual_sin_sum(a, d, n):\n",
      "    angles = np.arange(n) * d + a\n",
      "    return np.sum(np.sin(angles))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# When sin(d / 2) != 0\n",
      "print('cos', predicted_cos_sum(4, 0.2, 17), actual_cos_sum(4, 0.2, 17))\n",
      "print('sin', predicted_sin_sum(4, 0.2, 17), actual_sin_sum(4, 0.2, 17))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "cos 7.7038472261 7.7038472261\n",
        "sin -6.27049470825 -6.27049470825\n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# When sin(d / 2) ~ 0\n",
      "print('cos : sin(d/2) ~ 0;', predicted_cos_sum(4, np.pi * 2, 17), actual_cos_sum(4, np.pi * 2, 17))\n",
      "print('sin : sin(d/2) ~ 0;', predicted_sin_sum(4, np.pi * 2, 17), actual_sin_sum(4, np.pi * 2, 17))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "cos : sin(d/2) ~ 0; 7.85033095132 -11.1119415547\n",
        "sin : sin(d/2) ~ 0; 9.08928024892 -12.8656424202\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Proof"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The basic order of play is to rearrange the sum so that the terms in the current iteration of the sum cancel terms in the previous iteration, and we can therefore get rid of the sum.  This is a [telescoping series](https://en.wikipedia.org/wiki/Telescoping_series)."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We will do the cosine series first.  The sine proof is almost identical."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Cosine sum"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Following the notation of the [arithmetic progression of cosines paper](http://evergreen.loyola.edu/mpknapp/www/papers/knapp-sv.pdf), we remember that (angle sum rules):\n",
      "\n",
      "$$\n",
      "\\sin(A + B) = \\sin A \\cos B + \\cos A \\sin B \\\\\n",
      "\\sin(A - B) = \\sin A \\cos B - \\cos A \\sin B \\\\\n",
      "\\implies \\\\\n",
      "\\sin(A + B) - \\sin(A - B) = 2\\cos A \\sin B\n",
      "$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Let:\n",
      "\n",
      "$$\n",
      "C \\triangleq \\sum_{n=0}^{N-1}\\cos(a + nd)\n",
      "$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Only if $\\sin(d/2) \\ne 0$, we can safely multiply both sides by $2\\sin(d/2)$:\n",
      "\n",
      "$$\n",
      "2C \\sin(d / 2) = \\sum_{n=0}^{N-1}2 \\cos(a + nd) \\sin(d/2)\n",
      "$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Use angle sum result:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$$\n",
      "2C \\sin(d / 2) =\n",
      "\\sum_{n=0}^{N-1} \\sin(a + nd + d/2) - \\sin(a + nd - d/2) \\\\\n",
      "= \\sum_{n=0}^{N-1} \\sin \\bigg ( a + \\frac{2nd + d}{2} \\bigg ) - \\sin \\bigg ( a + \\frac{2nd - d}{2} \\bigg ) \\\\\n",
      "= \\sum_{n=0}^{N-1} \\sin \\bigg ( a + \\frac{(2n + 1)d}{2} \\bigg ) - \\sin \\bigg ( a + \\frac{(2n - 1)d}{2} \\bigg )\n",
      "$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now the series will telescope. Write:\n",
      "$$\n",
      "s_{2n-1} \\triangleq \\sin \\bigg ( a + \\frac{(2n - 1)d}{2} \\bigg ) \\\\\n",
      "s_{2n+1} \\triangleq \\sin \\bigg ( a + \\frac{(2n + 1)d}{2} \\bigg )\n",
      "$$\n",
      "\n",
      "The value of the sum when $n=k$ : $s_{2k + 1} - s_{2k - 1}$.\n",
      "\n",
      "The value of the sum when $n=k+1$ : $s_{2(k+1)+1} - s_{2(k+1) - 1} = s_{2k+3} - s_{2k+1}$\n",
      "\n",
      "Therefore the second term at each iteration cancels the first term at the previous iteration, and the sum retains only the first term from the last iteration and the second term from the first:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$$\n",
      "2C \\sin(d / 2) = \\sin \\bigg ( a + \\frac{(2(n - 1) + 1)d}{2} \\bigg ) - \\sin \\bigg ( a + \\frac{(2(0 - 1) + 1)d}{2} \\bigg ) \\\\\n",
      "= \\sin \\bigg ( a + \\frac{(2N - 1)d}{2} \\bigg ) - \\sin \\bigg ( a - \\frac{d}{2} \\bigg )\n",
      "$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now we go the opposite direction with the $\\sin(A + B) - \\sin(A - B) = 2\\cos A \\sin B$ rule.  We need to do some fancy footwork to get the arguments into $A \\pm B$ form:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$$\n",
      "2C \\sin(d / 2) = \\sin \\bigg ( a + \\frac{2Nd - d}{2} \\bigg ) - \\sin \\bigg ( a - \\frac{nd - d - nd}{2} \\bigg ) \\\\\n",
      "= \\sin \\bigg ( a + \\frac{(N - 1)d}{2} + \\frac{Nd}{2} \\bigg ) - \\sin \\bigg ( a + \\frac{(N - 1)d}{2} - \\frac{Nd}{2} \\bigg )\\\\\n",
      "= 2 \\cos \\bigg (a + \\frac{(N - 1)d}{2} \\bigg ) \\sin (Nd / 2)\n",
      "$$\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Then we solve for $C$ to finish the proof.\n",
      "\n",
      "$\\blacksquare$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Sine sum"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This is almost identical, but applying:\n",
      "\n",
      "$$\n",
      "\\cos(A + B) = \\cos A \\cos B - \\sin A \\sin B \\\\\n",
      "\\cos(A - B) = \\cos A \\cos B + \\sin A \\sin B \\\\\n",
      "\\implies \\\\\n",
      "\\cos(A + B) - \\cos(A - B) = -2 \\sin A \\sin B\n",
      "$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Let:\n",
      "\n",
      "$$\n",
      "S \\triangleq \\sum_{n=0}^{N-1}\\sin(a + nd)\n",
      "$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Only if $\\sin(d/2) \\ne 0$, we can safely multiply both sides by $-2 \\sin(d / 2)$ and continue with the same steps as for the cosine:\n",
      "\n",
      "$$\n",
      "-2S \\sin(d / 2) = \\sum_{n=0}^{N-1}-2 \\sin(a + nd) \\sin(d/2) \\\\\n",
      "= \\sum_{n=0}^{N-1} \\cos \\bigg ( a + \\frac{(2n + 1)d}{2} \\bigg ) - \\cos \\bigg ( a + \\frac{(2n - 1)d}{2} \\bigg ) \\\\\n",
      "= \\cos \\bigg ( a + \\frac{(2N - 1)d}{2} \\bigg ) - \\cos \\bigg ( a - \\frac{d}{2} \\bigg ) \\\\\n",
      "= -2 \\sin \\bigg (a + \\frac{(N - 1)d}{2} \\bigg ) \\sin (Nd / 2)\n",
      "$$\n",
      "\n",
      "Then solve for $S$.\n",
      "\n",
      "$\\blacksquare$"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}