Solving recurrence for number of moves M(n) = 2M(n-1) + 1, M(1) = 1 M(n) = 2M(n-1) + 1 = 2(2M(n-2) + 1) + 1 = 2^2*M(n-2) + 2^1 + 2^0 = 2^2*(2M(n-3) +
{"Image DocumentName": "Solving recurrence for number of moves", "Image ImageDescription": "M(n) = 2M(n-1) + 1, M(1) = 1. M(n) = 2M(n-1) + 1. = 2(2M(n-2) + 1) + 1 = 2^2 M(n-2) + 2^1 + 2^0. = 2^2 (2M(n-3) + 1) + 2^1 + 2^0. = 2^3 M(n-3) + 2^2 + 2^1 + 2^0. = \u2026 = 2^(n-1) M(1) + 2^(n-2) + \u2026 + 2^1 + 2^0. = 2^(n-1) + 2^(n-2) + \u2026 + 2^1 + 2^0. = 2^n - 1.", "Image XResolution": "37", "Image YResolution": "37", "Image ResolutionUnit": "Pixels/Centimeter", "Image Software": "SlidePlayer", "Image YCbCrPositioning": "Centered"}