Given is an array $A$ of positive integers with size $n$ and an array index $i$ (indexing starts at $1$). Prove using mathematical induction over $n$ that there always exists a contiguous subarray $S$ in $A$ such that the (sum of the elements of $S$) $\pmod {i} = 0.$
I get stuck halfway through the inductive step. Here is my work:
Let $p(n)$ denote the statement we're proving.
Base case: For $n = 1$ the statement holds (every positive integer mod $1 = 0$), so the subarray $S$ is the array $A$ itself.
Induction assumption: Suppose $p(n)$ is true.
Inductive step: For an array of size $n+1$ we consider the following two cases:
Case (1): $i \in \{1, 2, ..., n\}$. It follows directly from the inductive assumption that $p(n+1)$ is true (since $i \neq n+1$).
Case (2): $i = n+1$ (...).
This is where I get stuck, how would you argue that $S$ exists here?