Seeking proof using mathematical induction

Question

\begin{equation}a: \mathbb N ×\mathbb N \to \mathbb R \end{equation} where for all \begin{equation}x,y\in\mathbb N\end{equation}\begin{equation}a(x,y) =a(y,x)\end{equation} How do I show that the following equation is true? (using mathematical induction) \begin{equation} \sum_{b,c=0}^{n} a(b,c) = 2\sum_{0≤b<c≤n} a(b,c) +\sum_{b=0}^{n} a(b,b) \end{equation}

Answer 1

Case $n=1$ is shown in the comments.

Suppose that for $n=k$ is valid. Then

$\begin{align} \sum_{b,c=0}^{k+1} a(b,c) =& \sum_{b,c=0}^{k} a(b,c) + \sum_{b=0}^{k+1} a(b,k+1) + \sum_{c=0}^{k} a(k+1,c) \\= & 2\sum_{0≤b<c≤k} a(b,c) +\sum_{b=0}^{k} a(b,b) + \sum_{b=0}^{k+1}a(b,k+1)+ \sum_{c=0}^{k} a(k+1,c)\\= &2\sum_{0≤b<c≤k} a(b,c) +2\sum_{0\leq b<c\leq k+1}^{k}a(b,c) + \sum_{b=0}^{k} a(b,b) + a(k+1,k+1) \\= &2\sum_{0≤b<c≤k+1} a(b,c) +\sum_{b=0}^{k+1} a(b,b) \end{align}$.

Then is valid for $n=k+1$.

There you have it.

Answer 2

One natural way to think about this is to regard $a$ as an infinite matrix $A$ with $(b, c)$ entry $a(b, c)$. Since $a(b, c) = a(c, b)$ for all $b, c$, the matrix is equal to its formal transpose. Then, the inductive hypothesis says that sum of the entries in the $n \times n$ submatrix at the upper-left corner of $A$ is equal to the sum of the entries along the diagonal plus twice the sum of the entries above the diagonal. (Put this way, the claim is perhaps evident even without induction, but nevertheless let's carry on...)

The terms in the sum $\sum_{b, c = 0}^{n + 1} a(b, c)$ but not in $\sum_{b, c = 0}^n a(b, c)$ are the terms with at least one of $b, c$ equal to $n + 1$. By hypothesis $a(b, n + 1) = a(n + 1, b)$, and so for $b < n + 1$ the summands $a(b, n + 1)$ and $a(n + 1, b)$ agree and together they contribute $2 a(b, n + 1)$. The remaining term is $a(n + 1, n + 1)$. All that remains is to combine these two terms into the two sums that appear in the inductive step, which is just a matter of manipulating sigma notation.