Question 1158359
Base case: n=1. {{{(matrix(2,1,1,0))+(matrix(2,1,1,1))=1+1=2=2^1}}}. 
Induction step. Assume that {{{(matrix(2,1,k,0))+(matrix(2,1,k,1))}}}+...+{{{(matrix(2,1,k,k-1))+(matrix(2,1,k,k))=2^k}}}, for some arbitrary positive integer k. Lemma: {{{(matrix(2,1,k+1,j))=(matrix(2,1,k,j-1))+(matrix(2,1,k,j))}}}. <br/>{{{(k+1)!/(j!(k-j+1)!)=k!/((j-1)!(k-j+1)!)+k!/j!(k-j)!}}} <br/>{{{(k+1)!/(j!(k-j+1)!)=(k!*j)/(j!(k-j+1)!)+(k!*(k-j+1))/j!(k-j+1)!}}}<br/> {{{(k+1)!/(j!(k-j+1)!)=(k!*j)/(j!(k-j+1)!)+(k!*(k-j+1))/j!(k-j+1)!}}}<br/> {{{(k+1)!/(j!(k-j+1)!)=(k!*(j+k-j+1))/(j!(k-j+1)!)}}} <br/> {{{(k+1)!/(j!(k-j+1)!)=(k!*(k+1))/(j!(k-j+1)!)}}} <br/>  {{{(k+1)!/(j!(k-j+1)!)=(k+1)!/(j!(k-j+1)!)}}}. Therefore, {{{(matrix(2,1,k+1,j))=(matrix(2,1,k,j-1))+(matrix(2,1,k,j))}}}. We need to find {{{(matrix(2,1,k+1,0))+(matrix(2,1,k+1,1))}}}+...+{{{(matrix(2,1,k+1,k))+(matrix(2,1,k+1,k+1))}}} {{{(matrix(2,1,k+1,0))=1}}}. {{{(matrix(2,1,k+1,1))= (matrix(2,1,k,0))+ (matrix(2,1,k,1))}}}, {{{(matrix(2,1,k+1,2))= (matrix(2,1,k,1))+ (matrix(2,1,k,2))}}}, and so on. <br/> So {{{(matrix(2,1,k+1,0))+(matrix(2,1,k+1,1))}}}+...+{{{(matrix(2,1,k+1,k))+(matrix(2,1,k+1,k+1))=1+(matrix(2,1,k,0))+2(matrix(2,1,k,1))+2(matrix(2,1,k,2))}}}+...+{{{2(matrix(2,1,k,k))+(matrix(2,1,k,k+1))}}}. Since {{{(matrix(2,1,k,k+1))=0}}}, we can use our assumption and get {{{(matrix(2,1,k+1,0))+(matrix(2,1,k+1,1))}}}+...+{{{(matrix(2,1,k+1,k))+(matrix(2,1,k+1,k+1))=1+2^(k+1)-1=2^(k+1)}}}. The statement is proven.