Given is the Bubble sort algorithm
Bubblesort(A)
for i=1 to A.length
for j=A.length downto i+1
if A[j] < A[j-1]
exchange A[j] with A[j-1]
How do you prove that both these for loops will terminate?
I'm not sure how to prove that, I can only tell that the inner loop will terminate if j=j+1 and if you reach that, the length of the subarray will be increased by $1$ and the first element of the subarray will be its smallest because you swap A[i+1] with A[i].
The outer loop will terminate if i=A.length because there A[1...n] will include all elements in sorted order.
But how could this be proven? I think it should work with induction because you start at $1$ and walk step by step through the array till you reach its end, swap adjacent elements if condition is met but how would that look like? Or maybe there is a different way than induction too? :S
They both terminate simply because the length of $A$ is finite, so the algorithm goes through the outer loop exactly $length$ many times, while during each pass of the outer loop, the algorithm passes through the inner loop between $1$ and $length -1$ times ... which is therefore finite as well.
Of course, proving that when the algorithm is done, the array is sorted, is a little more difficult. But you're right: use induction to show that after $i$ passes of the outer loop, the elements $A[1]$ through $A[i]$ are sorted in increasing order, while the elements in $A[i+1]$ are all greater or equal to $A[i]$